飞翔的金鱼 @ 2018-02-08 18:04:09
#include <bits/stdc++.h>
using namespace std;
int n,m;
int w[70],v[70],q[70]; //w是价值,v是占用空间
int dp[32010],ok[70];
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++) {
scanf("%d%d%d",&w[i],&v[i],&q[i]);
int k=v[i];
v[i]=w[i];
w[i]*=k;
if (q[i]) ok[i]=1;
}
for (int i=1;i<=m;i++)
if (q[i]==0 || (q[i] && ok[i]==0))
for (int j=n;j>=v[i];j--)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
else if (q[i] && ok[i]) {
int ber=0;
for (int j=n;j>=v[i]+v[q[i]];j--)
if (dp[j-v[i]-v[q[i]]+w[i]+w[q[i]]]>dp[j]) {
dp[j]=dp[j-v[i]-v[q[i]]+w[i]+w[q[i]]];
ber=1;
}
if (ber)
for (int j=1;j<=n;j++)
if (q[j]==q[i]) ok[j]=0;
}
printf("%d",dp[n]);
return 0;
}
为什么本蒟蒻WA了七个点!!?? 大佬指教