A. 货币

思路

从“给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。”这句话中我们可以想到，货币是无限的，那我们就可以想到这道题目就是一个完全背包问题，只不过它只有体积和容量，且价值总和要正好等于容量的一个衍生问题。那我们可以这样想：

• 状态表示中dp[i][j]的集合就是从前i种货币里选，组成面值恰好是j的所有选法。
• 状态表示的属性就是方案数。

那状态计算又是什么呢，完全背包的状态计算是dp[j]=max(dp[j],dp[j-v]+w)，我们将价值去掉，max改成+=，再用完全背包优化后的版本，那状态计算就是dp[j]+=dp[j-v]，所以本题的状态计算就是：

• dp[j]+=dp[j-a[i]]。

代码

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

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

B. 小z的创业计划1与C. 小z的创业计划2

思路

这两道题其实就是最长上升子序列I与最长上升子序列II的模型，首先对于这道题目，我们可以这样：

• 状态表示中dp[i]来表示以i结尾的的子序列的长度是多少。
• 状态表示的属性就是选最大值。
• 状态计算就是在i中扫的时候，从后往前找到一个能接上的点j，那序列长度就是dp[j]+1。

这样写可以将B题AC，但C题却不能，因为C题的数据加强了，会超时，所以我们不妨优化一下，写成二分优化版本（具体是怎么优化的，请看讲义：讨论详情 - turing-code），所以我们可以这样：

• 状态表示中dp[i]来表示长度为i的的子序列，末尾的值是多少。
• 状态表示的属性就是选最大值。
• 状态计算就是a[i]要去找到最后一个小于它的数字。

代码

优化版本

B. 小z的创业计划1

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int m[N],p[N],dp[N];
int main(){
	freopen("cy1.in","r",stdin);
	freopen("cy1.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		int n,k;
		cin>>n>>k;
		dp[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) dp[i]=max(dp[i-1],dp[l]+p[i]);
			else dp[i]=max(dp[i-1],p[i]);
		}
		cout<<dp[n]<<endl;
	}
	return 0;
}

C. 小z的创业计划2

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int m[N],p[N],dp[N];
signed main(){
	freopen("cy2.in","r",stdin);
	freopen("cy2.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		int n,k;
		cin>>n>>k;
		dp[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) dp[i]=max(dp[i-1],dp[l]+p[i]);
			else dp[i]=max(dp[i-1],p[i]);
		}
		cout<<dp[n]<<endl;
	}
	return 0;
}

这两道题目完全没有思路，所以就放弃了，下一次不能轻易放弃。

D. 鸡蛋的硬度1与E. 鸡蛋的硬度2

思路

对于这两道题目，我们首先可以这样： 状态表示就是用dp[i][j]表示在i层楼，j个鸡蛋的测量方案中最大情况的最小值。 其中，j个鸡蛋在足够多的情况下可以不全部用完。

那状态计算就为：

1.不使用第j个鸡蛋，方案数为dp[i][j−1]。 2.使用第j个鸡蛋，则有1~i层共种情况可以扔，假设在第k层扔：

• 蛋碎：搜索区间变成 [1,k−1],鸡蛋数减少1，方案数为dp[k−1][j−1]。
• 蛋没碎：搜素区间变成[k+1,i],鸡蛋数不变，方案数为dp[i−k][j]。

这样写可以将D题AC，但E题却不能，因为E题的数据加强了，会超时，所以我们不妨优化一下，我们可以这样： 状态表示就是用dp[i][j]表示用j个鸡蛋测量i次能测量的区间长度的最大值。

那状态计算就为：

• 在某位置扔第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。

  代码

  朴素版本

  D. 鸡蛋的硬度1

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10,M=1e3+10;
int dp[N][M];
int main(){
freopen("eggs1.in","r",stdin);
freopen("eggs1.out","w",stdout);
int n,m;
while(cin>>n>>m){
for(int i=1;i<=n;i++) dp[i][1]=i;
for(int i=1;i<=m;i++) dp[1][i]=1;
for(int i=2;i<=n;i++)
for(int j=2;j<=m;j++){
dp[i][j]=dp[i][j-1];
for(int k=1;k<=i;k++) dp[i][j]=min(dp[i][j],max(dp[k-1][j-1],dp[i-k][j])+1);
}
cout<<dp[n][m];
}
return 0;
}

优化版本

E. 鸡蛋的硬度2

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10,M=1e3+10;
int dp[N][M];
int main(){
	freopen("eggs2.in","r",stdin);
	freopen("eggs2.out","w",stdout);
	int n,m;
	while(cin>>n>>m){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++) dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+1;
			if(dp[i][m]>=n){
				cout<<i<<endl;
				break;
			}
		}
	}
    return 0;
}

这两道题目完全没有思路，所以就放弃了，下一次不能轻易放弃。