Mars_Cat

建个转移方程即可。。但我建错了好多。。

#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

int n,mm;
int v[500],m[500];
int f1v[60],f2v[60],f1m[60],f2m[60];
int dp[32010];
int tt;

int Max(int xx,int yy)
{
	if(xx>yy) return xx;
	return yy;
}

int main()
{
	scanf("%d%d",&n,&mm);
	memset(dp,0,sizeof(dp));
	memset(v,0,sizeof(v));
	memset(m,0,sizeof(m));
	memset(f1v,0,sizeof(f1v));
	memset(f2v,0,sizeof(f2v));
	memset(f1m,0,sizeof(f1m));
	memset(f2m,0,sizeof(f2m));
	tt=mm;
	for(int i=1;i<=mm;++i)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		if(z==0)
		{
			v[i]=x*y;
			m[i]=x;
		}
		else
			if(f1v[z]==0)
			{
				f1v[z]=x*y;
				f1m[z]=x;
			}
			else
			{
				f2v[z]=x*y;
				f2m[z]=x;
			}
	}
	for(int i=1;i<=tt;++i)
		for(int j=0;j<=n-m[i];++j)
		{
			dp[j]=Max(dp[j],dp[j+m[i]]+v[i]);
			if(j+m[i]+f1m[i]<=n)
				dp[j]=Max(dp[j],dp[j+m[i]+f1m[i]]+v[i]+f1v[i]);
			if(j+m[i]+f2m[i]<=n)
				dp[j]=Max(dp[j],dp[j+m[i]+f2m[i]]+v[i]+f2v[i]);
			if(j+m[i]+f1m[i]+f2m[i]<=n)
				dp[j]=Max(dp[j],dp[j+m[i]+f1m[i]+f2m[i]]+v[i]+f1v[i]+f2v[i]);
		}
	int ans=0;
	for(int i=0;i<=n;++i)ans=Max(ans,dp[i]);
	printf("%d\n",ans);	
	return 0;
}