货币（DP）

思路没想到的原因

一直找错了方向，状态计算也推错了。以后一定一定要多积累$DP$的习题，因为这种题型很重要！！！

思路

这是一道完全背包的变形题。

状态表示： $f[i][j]$表示从前$i$种纸币里选恰好能组成面值为$j$的选法。在当我们算的时候，可以把$f[i][j]$优化成$f[j]$。

状态计算：$f[j]=f[j]+f[j-v]$，$v$表示输入的纸币面值。

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=3010,mod=1e9+7;
int n,m;
int f[tt],v;

int main(){
	freopen("money.in","r",stdin);
	freopen("money.out","w",stdout);
    cin >>n>>m;
    f[0]=1;
    for(int i=1;i<=n;i++){
    	cin >>v;
    	for(int j=v;j<=m;j++){
			f[j]=(f[j]+f[j-v])%mod;
        }
	}
    cout <<(f[m])%mod;
    return 0;

小z的创业计划1（DP）

思路没想到的原因

对$DP$的题型还不够熟练，以后要多练一练。

思路

用二分求出第一个（从后往前）距离$i$地址相差$>k$的元素，然后判断有没有这个点。

状态表示：$f[i]$表示从第一个距离$i$地址相差$>k$的元素的最大利润。

状态计算：

• 如果满足$m[i]-m[l]>k$，那么$f[i]=max(f[i-1],f[l]+p[i])$；
• 否则这个点不存在，$f[i]=max(f[i-1],p[i])$。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=110;
int m[tt],p[tt],f[tt];

signed main(){
	freopen("cy1.in","r",stdin);
	freopen("cy1.out","w",stdout);
	int t;
	cin >>t;
	while(t--){
		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 i=1;i<=n;i++){
			cin >>m[i];
		}
		for(int i=1;i<=n;i++){
			cin >>p[i];
		}
		for(int i=1;i<=n;i++){
			int l=1,r=i;
			while(l<r){
		        int mid=(l+r+1)>>1;
		        if(m[i]-m[mid]>k) l=mid;
		        else r=mid-1;
		    }
		    if(m[i]-m[l]>k){
		    	f[i]=max(f[i-1],f[l]+p[i]);
			}else{
				f[i]=max(f[i-1],p[i]);
			}
		}
		cout <<f[n]<<endl;
	}
	return 0;
}

小z的创业计划2（DP）

思路没想到的原因

对$DP$的题型还不够熟练，以后要多练一练。且与前一道题的唯一区别是数据范围。

思路

用二分求出第一个（从后往前）距离$i$地址相差$>k$的元素，然后判断有没有这个点。这道题的与上一道题的唯一区别就是要开$long$ $long$。

状态表示：$f[i]$表示从第一个距离$i$地址相差$>k$的元素的最大利润。

状态计算：

• 如果满足$m[i]-m[l]>k$，那么$f[i]=max(f[i-1],f[l]+p[i])$；
• 否则这个点不存在，把$f[l]$减去即可。$f[i]=max(f[i-1],p[i])$。

代码

#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;
	while(t--){
		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 i=1;i<=n;i++){
			cin >>m[i];
		}
		for(int i=1;i<=n;i++){
			cin >>p[i];
		}
		for(int i=1;i<=n;i++){
			int l=1,r=i;
			while(l<r){
		        int mid=(l+r+1)>>1;
		        if(m[i]-m[mid]>k) l=mid;
		        else r=mid-1;
		    }
		    if(m[i]-m[l]>k){
		    	f[i]=max(f[i-1],f[l]+p[i]);
			}else{
				f[i]=max(f[i-1],p[i]);
			}
		}
		cout <<f[n]<<endl;
	}
	return 0;
}

鸡蛋的硬度1（DP）

思路没想到的原因

这道题目在考试的时候思路错了，所以没写对，下一次要再多想想。

思路

状态表示：$f[i][j]$表示在$i$层楼，$j$个鸡蛋的测量方案中最坏情况的最小值。

状态计算： 在$f[k-1][j-1]$（蛋碎）与$f[i-k][j]$（蛋没碎）选一个最大值再$+1$（加上本次的一次），再和$f[i][j-1]$（不使用鸡蛋）选一个最小值。

代码

#include <bits/stdc++.h>
using namespace std;

int flag_1=0,flag_2=0,f[110][110];

int main(){
	freopen("eggs1.in","r",stdin);
	freopen("eggs1.out","w",stdout);
	int n,m;
	while(cin >>n>>m){
		flag_1=0,flag_2=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=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;
}

鸡蛋的硬度2（DP）

思路没想到的原因

这道题目在考试的时候感觉太难了，所以没写，下一次要再多想想。

思路

状态表示：$f[i][j]$表示$j$个鸡蛋测量i次能测量的区间长度的最大值。

状态计算：$f[i][j]=f[i-1][j]+f[i-1][j-1]$。

代码

#include <bits/stdc++.h>
using namespace std;

int flag_1=0,flag_2=0,f[2010][3010];

int main(){
	freopen("eggs2.in","r",stdin);
	freopen("eggs2.out","w",stdout);
	int n,m;
	while(cin >>n>>m){
		flag_1=0,flag_2=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){
					flag_2=1;
					cout <<i-1<<endl;
					flag_1=1;
					break;
				} 
			}
			if(flag_1==1) break;
		}
		if(flag_2==0){
			cout <<f[n][m]<<endl;
		}
	}
	return 0;
}

谢谢