题目传送门

A 货币

B 小z的创业计划1

C 小z的创业计划2

D 鸡蛋的硬度1

E 鸡蛋的硬度2

T1货币

没写全校暴0

思路

完全背包模版题，只是由最大价值变为了方案数，价值也没了，（注意在计算时要+=，不是=max(），是总方案数，不是求最大价值),其他基本一样（要f[1]=0）注意第二个循环要正着来

代码

#include<bits/stdc++.h>
using namespace std;
int f[3333],a,b,n,m,mo=1e9+7; 
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>>a;
		for(int j=a;j<=m;j++)f[j]+=(f[j-a]),f[j]%=mo;
	}
	cout<<f[m]%mo;
}

T2/T3小z的创业计划

思路

1.普通版本

f[i]代表以i结尾最大利润，我们可以枚举i,j的两家店，如果距离满足则可以选（有条件），也可以不选（无条件），最后再去这一段利润的最大值就可以了每个店初始化为这个店的利润。

2.优化版本

大体跟第一种差不多，只不过把暴力循环改为了二分优化

代码

这里只给优化版本，普通版本太简单

#include<bits/stdc++.h>
using namespace std;
long long a[200010],f[200010],b[200010],n,k;
int main(){
	freopen("cy2.in","r",stdin);
	freopen("cy2.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		cin>>n>>k;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++)cin>>b[i];
		f[0]=-2e9;
		for(long long i=1;i<=n;i++){
			long long l=1,r=i;
			while(l<r){
				int m=(l+r+1)>>1;
				if(a[i]-a[m]>k)l=m;
				else r=m-1;
			}
			if(a[i]-a[l]>k){
				f[i]=max(f[i-1],f[l]+b[i]);
			}
			else{
				f[i]=max(f[i-1],b[i]);
			}
		}
		cout<<f[n]<<"\n";
	}
}

T4/T5鸡蛋的硬度

思路

1.普通写法

f[i][j]表示第i层，扔j个鸡蛋最坏扔几次,我们可以用枚举写，先初始化（1个鸡蛋x楼要x次，x个鸡蛋1层楼1次）在k$(1<=k<=i)$层时我们可以扔或不扔,扔有可能碎或不碎 注意扔和不扔是我们主观的要取最小值，而碎和不碎是有题目规定最坏的，取最大值

优化写法

由于枚举k会超时所以我们可以直接计算，i个鸡蛋测j次最大能测几层楼，在某层扔可能碎或不碎，注意这两种情况不相交，所以要相加，还要加上这一层

代码

#include<bits/stdc++.h>
using namespace std;
int f[3333][3333];
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++)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]<<"\n";
	}
	return 0;	
}

#include<bits/stdc++.h>
using namespace std;
int f[3333][3333];
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++)f[i][1]=i;
		for(int i=1;i<=m;i++)f[1][i]=1;
		int l;
		l=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){
					cout<<i-1<<"\n";
					l=1;
					break;
				}	
			}
			if(l)break;
		}
		if(!l)cout<<f[n][m]<<"\n";
	}
	return 0;	
}