zsm____yi @ 2018-11-30 17:27:07
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct node{
int v1[4];
int w1[4];
int f1=0;
}jm[200];
int n,k,m,w[200],v[200],f[200],dp[33000][200];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&v[i],&w[i],&f[i]);
w[i]=v[i]*w[i];
}
for(int i=1;i<=m;i++){
if(f[i]==0){
k++;
jm[k].v1[0]=v[i];
jm[k].w1[0]=w[i];
jm[k].f1++;
}else{
jm[f[i]].v1[jm[f[i]].f1]=v[i];
jm[f[i]].w1[jm[f[i]].f1]=w[i];
jm[f[i]].f1++;
}
}
int v0[4],w0[4];
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
if(jm[i].v1[0]<j){ dp[j][i]=dp[j][i-1];}else{
v0[0]=jm[i].v1[0];
w0[0]=jm[i].w1[0];
v0[1]=jm[i].v1[0]+jm[i].v1[1];
v0[2]=jm[i].v1[0]+jm[i].v1[2];
v0[3]=jm[i].v1[0]+jm[i].v1[2]+jm[i].v1[1];
w0[1]=jm[i].w1[0]+jm[i].w1[1];
w0[2]=jm[i].w1[0]+jm[i].w1[2];
w0[3]=jm[i].w1[0]+jm[i].w1[2]+jm[i].w1[1];
dp[j][i]=max(dp[j][i-1],dp[j-v0[0]][i-1]+w0[0]);
for(int q=1;q<=jm[i].f1;q++){
if(j>=v0[q]){ dp[j][i]=max(dp[j][i],dp[j-v0[q]][i-1]+w0[q]); }
}
}
}
}
printf("%d",dp[n][k]);
return 0;
}
编译第46行有问题,但不知道哪有问题,向大佬求助
by zsm____yi @ 2018-11-30 17:31:21
dp[j][i]=max(dp[j][i-1],dp[j-v0[0]][i-1]+w0[0]); 这句问题,看不出;