货币

本题是一道dp题（背包）

按照老师的思路，我们要画出状态转移DP图

看不了？没事，我们一遍遍推！

我们要思考DP中的三要素：状态表示、初始化、状态转移方程：

1. 先思考状态表示，我在这里想的是用f[i]来表示到第i个的所有方案。也可以不一样，因为状态表示不是唯一。
2. 状态表示：$f_i$，集合：到第i个的所有方案。属性：方案
3. 初始化：$f_0=1$;因为全不选也是种选择。
4. 状态转移方程：$f[i-1]+f[j-x]$;因为$j-x$是为了找到和他匹配的数量

j从x循环到m因为保不齐什么时候会用。

#include<bits/stdc++.h>
	using namespace std;
	long long f[3010];
	const long long mod=1e9+7;
	int main(){
		freopen("money.in","r",stdin);
		freopen("money.out","w",stdout);
		f[0]=1;
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			int x;
			cin>>x;
			for(int j=x;j<=m;j++){
				f[j]=(f[j-x]+f[j])%mod;
			}
		}
		cout<<f[m]%mod;
		return 0;
	}

小z的创业计划（共两题）

这题小z去创业不开编程班了？

依旧是从状态转移方程、初始化、状态表示等三方面来讲诉

1. 状态表示：$f[i]$，集合：1到i的利润方案。属性：MAX
2. 初始化：$f[0]=-∞$，因为无论如何也不能让0来加入
3. 状态转移方程：$f[i]=max(f[i-1],f[l]+p[i])$;
4. (附录)：l是用二分来求在1~i中，与i的距离大于k的地方。

#include<bits/stdc++.h>
using namespace std;
long long a[100010],f[100010],b[100010];
int main(){
	int t;
	cin>>t;
	while(t--){
		memset(a,0,sizeof a);
		memset(f,0,sizeof f);
		memset(b,0,sizeof b);
		int n,k;
		cin>>n>>k;
		f[0]=-2e9;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		for(int i=1;i<=n;i++){
			cin>>b[i];
		}
		for(int i=1;i<=n;i++){
			int l=1,r=i;
			while(r>l){
				int mid=l+r+1>>1;
				if(a[i]-a[mid]-1>=k){
					l=mid;
				}else{
					r=mid-1;
				}
			}
			if(a[i]-a[l]-1>=k){
				f[i]=max(f[i-1],f[l]+b[i]);
			}else{
				f[i]=max(f[i-1],b[i]);
			}
		}
		cout<<f[n]<<endl;
	}
	return 0;
}

(按题目要求写freopen)

鸡蛋的硬度1

本题依旧是dp

1. 状态表示：$f[i][j]$，集合：在i层楼，j个鸡蛋的测量方案。属性：最坏情况的最小值。 （附）其中j个鸡蛋在足够多的情况下可以不全部用完。

2. 初始化：$f[i][1]=i$，因为只有一个鸡蛋时只有一层一层试才保险，$f[1][i]=1$，因为层数只有1时只用扔一次。

3. 状态转移方程：

   • 蛋碎：区间范围减一，变成$f[k−1][j−1]$
   • 没碎：搜素区间减一,鸡蛋数不变，方案数$f[i−k][j]$

   所以方程为：$f[i][j]=min(f[i][j],max(f[k-1][j-1],f[i-k][j])+1)$

鸡蛋硬度2

1. 状态表示：$f[i][j]$，集合：表示用j个鸡蛋测量i次能测量的区间长度。属性：最大值。
2. 初始化：f[i][1]=i,f[1][i]=1;
3. 状态转移方程：

• 在某位置扔第j个鸡蛋后：
• 蛋碎，那么接下来还有j−1个蛋，i−1次，即f[i−1][j−1]
• 蛋不碎：f[i−1][j]
• 碎和不碎是不同的情况，二者计算的最长区间没有交集 因此要相加
• 加上本次的一次
• 所以最终状态转移方程：f[i][j]=f[i-1][j]+f[i-1][j-1]+1

#include<bits/stdc++.h>
using namespace std;
int f[2010][1010];
int main(){
	freopen("eggs2.in","r",stdin);
	freopen("eggs2.out","w",stdout);
	int n,m;
	while(cin>>n>>m){
		int flag1=0,flag2=0;
		memset(f,0,sizeof f);
		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]+1;
				if(f[i][m]>=n){
					cout<<i<<endl;
					flag1=1;
					flag2=1;
					break;
				}
			}
			if(flag1){
				break;
			}
		}
		if(!flag2){
			cout<<f[n][m]<<endl;
		}
	}
	return 0;
}