每日作者附：今天都吃了个大大的鸭蛋(阿巴阿巴真好吃)DP急需加强（好像短时间也做不到 假期再努力搞下ba）
T1货币
总结（自己）
wuaa没看出来是完全背包，一开始的思路就是错的 还做了3个小时（一开始的思路是每个面额都可以从面额-每张纸币的面额来 但没法去重所以是错的）
思路
完全背包模板题，只是变成了求方案数而已（还不需要求价值了）
附AC代码(用滚动数组写的)
#include<bits/stdc++.h>
using namespace std;
long long n,m,f[101000],a[101000];
const int Mod=1e9+7;
int main()
{
freopen("money.in","r",stdin);
freopen("money.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
f[0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[j]=(f[j]+f[j-a[i]])%Mod;
}
}
cout<<f[m];
return 0;
}
T2小z的创业计划1
总结（自己）
时间全去搞第1题了，没时间搞其它题了（有些题我都没看）
思路
dp三要素 f[i]定义 从1到i的最大利润
初始化 f[0]=-2e9(不选店铺建造时要设为极小值)
递推式 要用二分查找一个l优化时间（l的定义是最接近i的位置）（本来的此题写法实在没时间了 后面会补）
如果w[i]-w[l]>k 那么f[i]=max(f[i-1],f[l]+q[i])（两者距离超过k，可以建造） f[i]=max(f[i-1],q[i])（离第一个位置的距离都比k小，要么只建自己，要么不要自己）
附Ac代码
#include<bits/stdc++.h>
using namespace std;
long long n,k,m,f[101000],w[101000],q[101000];
int main()
{
freopen("cy1.in","r",stdin);
freopen("cy1.out","w",stdout);
int t;
cin>>t;
while(t--){
memset(f,0,sizeof(f));
memset(w,0,sizeof(w));
memset(q,0,sizeof(q));
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>w[i];
}
for(int i=1;i<=n;i++){
cin>>q[i];
}
f[0]=-2e9;
for(int i=1;i<=n;i++){
int l=1,r=i;
while(l<r){
int mid=(l+r+1)>>1;
if(w[i]-w[mid]>k) l=mid;
else r=mid-1;
}
if(w[i]-w[l]>k){
f[i]=max(f[i-1],f[l]+q[i]);
}
else{
f[i]=max(f[i-1],q[i]);
}
}
cout<<f[n]<<endl;
}
return 0;
}
T3小z的创业计划2
总结（自己）
同上
思路
同上
附代码：
//同上
T4鸡蛋的硬度1
总结（自己）
同上
思路
Dp三要素
f[i][j]定义 共i层楼扔j个蛋判断出来的最坏情况的次数
初始化：f[i][1]=i(1个蛋i层最坏要扔i次) f[1][i]=1（一层楼不管多少个蛋都只扔一次）
递推式：枚举次数i 蛋数j和扔的楼层k 每次要先继承状态 那么在第k层扔有两情况：
没碎： （楼层在k层以下）
碎了：（楼层在k层以上且蛋碎了）
附Ac代码
#include<bits/stdc++.h>
using namespace std;
int n,m,f[1010][1010];
int main()
{
freopen("eggs1.in","r",stdin);
freopen("eggs1.out","w",stdout);
while(cin>>n>>m){
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=1;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]<<endl;
}
return 0;
}
T5鸡蛋的硬度2
总结（自己）
同上
思路
Dp三要素
f[i][j]定义 共i层楼扔j个蛋能判断的最大距离 答案：第一个f[i][j]>m的i
初始化 f[i][1]=i(1个蛋i层最坏要扔i次) f[1][i]=1（一层楼不管多少个蛋都只扔一次）和上面一样
递推式： 不管从哪层楼扔下去 都会有碎（f[[i-1][j-1]）和不碎(f[i-1][j])两种情况而碎和不碎是两个永远不会相交的答案区间所以要相加 所以： f[i][j]=f[i-1][j-1]+f[i-1][j];
最后还有个小细节 有些时候不会输出（比如m=1)所以循环中没有输出时应输出f[n][m]
附AC代码
#include<bits/stdc++.h>
using namespace std;
long long n,k,m,f[2010][2010],a[201000];
int main()
{
freopen("eggs2.in","r",stdin);
freopen("eggs2.out","w",stdout);
while(cin>>n>>m){
for(int i=1;i<=n;i++) f[i][1]=i;
for(int i=1;i<=m;i++) f[1][i]=1;
bool o=0;
for(int i=2;i<=n;i++){
for(int j=2;j<=m;j++){
f[i][j]=f[i-1][j-1]+f[i-1][j];
if(f[i][m]>=n)
{
o=1;
cout<<i-1<<endl;
break;
}
}
if(f[i][m]>=n) break;
}
if(o==0)
{
cout<<f[n][m]<<endl;
}
}
return 0;
}
