Quasimodo @ 2017-10-04 23:56:28
代码是参照题解区一位大佬思路写出来的,在循环枚举物品的时候,第一次是顺序(1~n),wa了第六个点,xjb改成了(n~1)就ac掉了,请教一下为什么啊
####include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int dp[35000];
int n,m;
int ac[35000],aw[35000],bc[35000][5],bw[35000][5];
int v,p,q;
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>v>>p>>q;
if(!q)
{
ac[i]=v;
aw[i]=v*p;
}
else
{
bc[q][0]++;
bc[q][bc[q][0]]=v;
bw[q][bc[q][0]]=v*p;
}
}
memset(dp,0,sizeof(dp));
for(int i=m;i>=1;i--)//这个位置
for(int j=n;j>0;j--)
{
dp[j]=max(dp[j],dp[j-ac[i]]+aw[i]);
if(j-ac[i]<bc[i][1]&&j-ac[i]<bc[i][2])
break;
else
{
if(j>=ac[i]+bc[i][1])
dp[j]=max(dp[j],dp[j-ac[i]-bc[i][1]]+aw[i]+bw[i][1]);
if(j>=ac[i]+bc[i][2])
dp[j]=max(dp[j],dp[j-ac[i]-bc[i][2]]+aw[i]+bw[i][2]);
if(j>=ac[i]+bc[i][1]+bc[i][2])
dp[j]=max(dp[j],dp[j-ac[i]-bc[i][1]-bc[i][2]]+aw[i]+bw[i][1]+bw[i][2]);
}
}
cout<<dp[n]<<endl;
return 0;
}