动态规划

总结：

目前只讲了基础的线性dp,首先是数字三角形，很多是从中变形过来的，如寒假训练的C题链接，然后就是类似最长上升子序列之类，这种的状态转移方程式就要想一会如寒假F，G,H.最后就是各种背包问题，如A,B,D,E,K.

B - CD

传送门
基础01背包问题，物体的体积同时也是物体的质量。
要打印所选物体，那lst记录一下最后一个选择的物体，然后倒推回去就好了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
int n,m,v[10010],maxn,u,s;
struct stu{
	int w,lst;
}f[10010];
int main(){
	while(scanf("%d",&n)!=EOF){
		maxn=0;
		memset(f,0,sizeof(f));
		scanf("%d",&m);
		for(int i=1;i<=m;i++){
			scanf("%d",&v[i]);
		}
		for(int i=1;i<=m;i++){
			for(int j=n;j>=v[i];j--){
				if(f[j].w<f[j-v[i]].w+v[i]){
					f[j].w=f[j-v[i]].w+v[i];
					f[j].lst=i;	
				}
			}
		}
		
		for(int i=1;i<=n;i++){
			if(maxn<f[i].w){
				maxn=f[i].w;
				u=i;
				s=f[i].lst;
			}
		}
	//	printf("%d\n",maxn);
		while(u){
			printf("%d ",v[s]);
			u-=v[s];
			s=f[u].lst;
			
		}
		printf("sum:%d\n",maxn);
	}
	return 0;
}

k-硬币

传送门
多重背包模板题，数据范围较大，O(n*n)的复杂度无法完成，好像可用单调队列优化，但显然我不会。但此为可行性问题，无需关注前面选的最大值，当前能选值必须从上一个能选值推出来就很神奇。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
int n,m,used[100010],ans;
bool f[100010];
int a[110],c[110];
int main(){

	while(scanf("%d%d",&n,&m)&&n&&m){
		for(int i=1;i<=m;i++)f[i]=false;
		f[0]=true;
		ans=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		for(int i=1;i<=n;i++){
			scanf("%d",&c[i]);
		}
		for(int i=1;i<=n;i++){
			for(int j=0;j<=m;j++)used[j]=0;
			for(int j=a[i];j<=m;j++){
				if(!f[j]&&f[j-a[i]]&&used[j-a[i]]<c[i]){
					f[j]=true;
					used[j]=used[j-a[i]]+1;
				}
			}
		}
		for(int i=1;i<=m;i++){
			if(f[i]==true){
				//printf("%d ",i);
				ans++;
			}//printf("\n");
		}
		printf("%d\n",ans);
	} 
	return 0;
}

E划分

传送门
硬币分成等额的两份，所以一份便是sum/2，之后变与上面硬币那题一样了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
int c[10],used[210010],sum,tt;
bool f[210010];
int main(){
	while(scanf("%d%d%d%d%d%d",&c[1],&c[2],&c[3],&c[4],&c[5],&c[6])&&(c[1]||c[2]||c[3]||c[4]||c[5]||c[6])){
		sum=0;
		tt++;
		for(int i=1;i<=6;i++){
			sum+=i*c[i];
		}	
		if(sum%2){
			printf("Collection #%d:\n",tt);
			printf("Can't be divided.\n\n");
			continue;
		}
		for(int i=1;i<=sum/2;i++)f[i]=false;
		f[0]=true;
		for(int i=1;i<=6;i++){
			for(int j=0;j<=sum/2;j++)used[j]=0;
			for(int j=i;j<=sum/2;j++){
				if(!f[j]&&f[j-i]&&used[j-i]<c[i]){
					f[j]=true;
					if(j==sum/2){
						break;	
					}
					used[j]=used[j-i]+1;
				}
			} 
		}
		if(f[sum/2]){
			printf("Collection #%d:\n",tt);
			printf("Can be divided.\n\n");
		}else{
			printf("Collection #%d:\n",tt);
			printf("Can't be divided.\n\n");
		}
	} 
	return 0;
}