😕DAY15 DP专题
T1货币（题目传送门）
思路
状态表示:f[i][j]表示前i种货币能组成面值为j的所有选法
状态计算: 如果不用第i种货币:有f[i-1][j]种选法
如果使用第i种货币: 有f[i][j-ai]种选法 有f[i][j-2ai]种选法 有f[i][j-3ai]种选法 ..... 有f[i][j-kai]种选法
把他们加起来
f[i][j]=f[i-1][j]+f[i][j-ai]+f[i][j-2ai]+....+f[i][j-kai]
初始化: f[i][0]=1
🎈代码
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
long long f[1010][3010],a[1010];
int main()
{
freopen("money.in","r",stdin);
freopen("money.out","w",stdout);
int n,m;
cin>>n>>m;
for(int i=0;i<=n;i++)
{
f[i][0]=1;
}
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j]%MOD;
if(j>=a[i]) f[i][j]+=f[i][j-a[i]]%MOD;
}
}
cout<<(f[n][m]+MOD)%MOD;
return 0;
}
T2小z的创业计划1（题目传送门）
思路
状态表示:f[i]表示已i为止的利润
状态计算: 如果有一个离i最近且之间距离>k的点 那么 f[i]=max(f[l]+p[i],f[i-1])
否则 f[i]=max(p[i],f[i-1])
初始化: 要找出最大值，需要先赋一个最小值
为了避免影响需用memset将所有数组赋为0
🎈代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int tt=1e5+10;
int m[tt],p[tt],f[tt];
signed main()
{
freopen("cy2.in","r",stdin);
freopen("cy2.out","w",stdout);
int t;
cin>>t;
for(int i=1;i<=t;i++)
{
memset(m,0,sizeof m);
memset(p,0,sizeof p);
memset(f,0,sizeof f);
int n,k;
cin>>n>>k;
f[0]=-2e9;
for(int j=1;j<=n;j++)
{
cin>>m[j];
}
for(int j=1;j<=n;j++)
{
cin>>p[j];
}
for(int j=1;j<=n;j++)
{
int l=1,r=j;
while(l<r)
{
int mid=(l+r+1)>>1;
if(m[j]-m[mid]>k) l=mid;
else r=mid-1;
}
if(m[j]-m[l]>k) f[j]=max(f[j-1],f[l]+p[j]);
else f[j]=max(f[j-1],p[j]);
}
cout<<f[n]<<endl;
}
return 0;
}
T3 小z的创业计划2（题目传送门）
思路
状态表示:
状态计算: 如果有一个离i最近且之间距离>k的点 那么 f[i]=max(f[l]+p[i],f[i-1])
否则 f[i]=max(p[i],f[i-1])
初始化: 要找出最大值，需要先赋一个最小值
为了避免影响需用memset将所有数组赋为0
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int tt=1e5+10;
int m[tt],p[tt],f[tt];
signed main()
{
freopen("cy2.in","r",stdin);
freopen("cy2.out","w",stdout);
int t;
cin>>t;
for(int i=1;i<=t;i++)
{
memset(m,0,sizeof m);
memset(p,0,sizeof p);
memset(f,0,sizeof f);
int n,k;
cin>>n>>k;
f[0]=-2e9;
for(int j=1;j<=n;j++)
{
cin>>m[j];
}
for(int j=1;j<=n;j++)
{
cin>>p[j];
}
for(int j=1;j<=n;j++)
{
int l=1,r=j;
while(l<r)
{
int mid=(l+r+1)>>1;
if(m[j]-m[mid]>k) l=mid;
else r=mid-1;
}
if(m[j]-m[l]>k) f[j]=max(f[j-1],f[l]+p[j]);
else f[j]=max(f[j-1],p[j]);
}
cout<<f[n]<<endl;
}
return 0;
}
T4 鸡蛋的硬度1（题目传送门）
思路
状态表示: f[i][j]表示有i层j个鸡蛋扔的次数
状态计算: 不扔第j个鸡蛋:f[i][j]=f[i][j-1]
扔第j个鸡蛋： 在第1层扔 { 碎了 f[0][j-1] 没碎 f[i-1][j] } 在第2层扔 { 碎了 f[1][j-1] 没碎 f[i-2][j] } 在第k层扔 { 碎了 f[k-1][j-1] 没碎 f[i-k][j] } .......
f[i][j]=f[i][j-1]
还要加上扔的一次
f[i][j]=min(f[i][j],max(f[k-1][j-1],f[i-k][j])+1)
初始化： 因为只有一层，扔几次，都只有一次 f[1][j]=1
因为只有一个鸡蛋，只能一层一层扔 f[i][1]=i
🎈代码
#include<bits/stdc++.h>
using namespace std;
int f[110][11],flag,flag2;
int main()
{
//freopen("eggs1.in","r",stdin);
//freopen("eggs1.out","w",stdout);
int n,m,sum=0;
while(cin>>n>>m)
{
flag=0;
flag2=0;
for(int i=1;i<=n;i++)
{
f[i][1]=i;
}
for(int i=1;i<=m;i++)
{
f[1][i]=1;
}
for(int i=2;i<=n;i++)
{
for(int j=2;j<=m;j++)
{
f[i][j]=f[i][j-1];
for(int k=2;k<=i;k++)
{
f[i][j]=min(f[i][j],max(f[k-1][j-1],f[i-k][j])+1);
}
}
}
cout<<f[n][m];
}
}
T5鸡蛋的硬度2（题目传送门）
思路
状态表示 f[i][j]表示扔i次j个鸡蛋能测量的最大区间长度
状态计算 不扔第j个鸡蛋:f[i][j]=f[i][j-1]
扔第j个鸡蛋
碎了 f[i-1][j-1] 没碎 f[i-1][j]
它们是两个不交集的区间 设 扔的楼层为x 一个是 1 到 x-1 另一个是 x+1到 n 不是交集的
f[i][j]=f[i][j-1]
f[i][j]=f[i-1][j-1]+f[i-1][j]+1 (如果比n大就退出)
初始化 因为只扔一次，无论多少个鸡蛋，都只能测出1的长度 f[1][j]=1
因为只有一个鸡蛋，一次只能测1的长度,所以i次长度就是i f[i][1]=i
🎈代码
#include<bits/stdc++.h>
using namespace std;
int f[1100][11],flag,flag2;
int main()
{
//freopen("eggs1.in","r",stdin);
//freopen("eggs1.out","w",stdout);
int n,m,sum=0;
while(cin>>n>>m)
{
flag=0;
flag2=0;
for(int i=1;i<=n;i++)
{
f[i][1]=i;
}
for(int i=1;i<=m;i++)
{
f[1][i]=1;
}
for(int i=2;i<=n;i++)
{
for(int j=2;j<=m;j++)
{
f[i][j]=f[i-1][j]+f[i-1][j-1];
if(f[i][m]>=n)
{
flag2=1;
cout<<i-1<<endl;
flag=1;
break;
}
}
if(flag==1) break;
}
if(flag2==0) cout<<f[n][m]<<endl;
}
}
