A1263 友好城市

# include<iostream>
# include<map>
# include<algorithm>
using namespace std;
# define p pair<int,int>
# define m(a,b) make_pair(a,b)

const int N=5e3+5,M=1e4+5;
int n,a[N],dp[N],x,y,ans;
p f[N];

int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>x>>y;
		f[i]=m(x,y);
	}
	sort(f+1,f+n+1);
	for(int i=1;i<=n;++i){
		a[i]=f[i].second;
		dp[i]=1;
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<i;++j)
			if(a[j]<=a[i])
				dp[i]=max(dp[i],dp[j]+1);
	for(int i=1;i<=n;++i) ans=max(ans,dp[i]);
	cout<<ans;
	return 0;
}

P1541 乌龟棋（B1167）

# include<iostream>
using namespace std;

const int N=355;
int n,m,a[N],b[5],t,ans;
int dp[N][45][45][45];

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=m;++i){
		cin>>t;
		++b[t];
	}
	for(int x=1;x<=n;++x)
		for(int i=0;i<=b[2];++i)
			for(int j=0;j<=b[3];++j)
				for(int k=0;k<=b[4];++k){
					int l=x-i*2-j*3-k*4-1;
					int &f=dp[x][i][j][k];
					if(l<0||l>b[1]) continue;
					f=a[x];
					if(i!=0&&x>2) f=max(f,dp[x-2][i-1][j][k]+a[x]);
					if(j!=0&&x>3) f=max(f,dp[x-3][i][j-1][k]+a[x]);
					if(k!=0&&x>4) f=max(f,dp[x-4][i][j][k-1]+a[x]);
					if(l!=0&&x>1) f=max(f,dp[x-1][i][j][k]+a[x]);
				}
	for(int i=0;i<=b[2];++i)
		for(int j=0;j<=b[3];++j)
			for(int k=0;k<=b[4];++k){
				int l=n-i*2-j*3-k*4-1;
				int &f=dp[n][i][j][k];
				if(l<0||l>b[1]) break;
				ans=max(ans,f);
			}
	cout<<ans;
	return 0;
}

改（记忆化搜索）

# include<iostream>
using namespace std;

const int N=355,M=45;
int n,m,a[N],t,b[5];
int dp[M][M][M][M];

int f(int x,int t1,int t2,int t3,int t4){
	int &p=dp[t1][t2][t3][t4];
	int m=0;
	if(p!=0) return p;
	if(x==1) return dp[0][0][0][0]=a[1];
	if(t1>0) m=max(f(x-1,t1-1,t2,t3,t4),m);
	if(t2>0) m=max(f(x-2,t1,t2-1,t3,t4),m);
	if(t3>0) m=max(f(x-3,t1,t2,t3-1,t4),m);
	if(t4>0) m=max(f(x-4,t1,t2,t3,t4-1),m);
	return p=m+a[x];
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=m;++i){
		cin>>t;
		b[t]++;
	}
	cout<<f(n,b[1],b[2],b[3],b[4]);
	return 0;
}

P1049 装箱问题

# include<iostream>
# include<cstdio>
# include<cstring>
using namespace std;

int m,n,w[105],dp[20005];

int main(){
	scanf("%d %d",&m,&n);
	for(int i=0;i<n;++i) scanf("%d",w+i);
	for(int i=0;i<n;++i){
		for(int j=m;j>=w[i];--j) dp[j]=max(dp[j],dp[j-w[i]]+w[i]);
	}
	printf("%d",m-dp[m]);
	return 0;
}

A1292 宠物小精灵之收服

# include<iostream>
using namespace std;

int n,m,p,a,b,c,r;
int dp[1005][505];
/* 
使用至多i个精灵球，皮卡丘使用体力<=j时， 
收服小精灵最多的数量 
*/ 

int main(){
	cin>>m>>p>>n;
	for(int i=1;i<=n;++i){
		cin>>a>>b;
		for(int j=m;j>=a;--j)
			for(int k=p;k>b;--k)
				dp[j][k]=max(dp[j][k],dp[j-a][k-b]+1);
	}
	for(int i=1;i<=p;++i){
		if(dp[m][i]>c){
			c=dp[m][i];
			r=i;
		}
	}
	cout<<c<<" "<<p-r+1;
	return 0;
}

A1299 糖果

# include<iostream>
using namespace std;

const int N=105;//糖果种数 
int n,k,w;
int dp[N][N];
/*
前i件产品取部分总数量模k余j时
糖果总数的最大值
*/ 

int main(){
	cin>>n>>k;
	for(int i=1;i<k;++i)
		dp[0][i]=-1e9;
	for(int i=1;i<=n;++i){
		cin>>w;
		for(int j=0;j<k;++j)
			dp[i][j]=max(dp[i-1][j],dp[i-1][((j-w)%k+k)%k]+w);
	}
	cout<<dp[n][0];
	return 0;
}