baka @ 2017-09-24 15:48:23
#include <iostream>
using namespace std;
#define N 33000
#define M 66
#include <vector>
int v[M];
#include <cstdio>
int f[M][N];
int w[M];
vector<int> attatch[M];
#include <cstring>
int isAttatched[M];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int q;
scanf("%d%d%d",v+i,w+i,&q);
if(q) attatch[q].push_back(i);
isAttatched[i]=q;
}
memset(f,0,sizeof f);
f[0][0]=0;
for(int i=1;i<=m;i++){
if(isAttatched[i]) continue;
for(int j=v[i];j<=n;j++){
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+v[i]*w[i]);
if(attatch[i].size()>=1 && j>=v[i]+v[attatch[i][0]]){
f[i][j]=max(f[i][j],f[i-1][j-v[i]-v[attatch[i][0]]]+(v[i]*w[i]+v[attatch[i][0]]*w[attatch[i][0]]));
}
if(attatch[i].size()==2){
if(j>=v[i]+v[attatch[i][1]]){
f[i][j]=max(f[i][j],f[i-1][j-v[i]-v[attatch[i][1]]]+(v[i]*w[i]+v[attatch[i][1]]*w[attatch[i][1]]));
}
if(j>=v[i]+v[attatch[i][1]]+v[attatch[i][0]]){
f[i][j]=max(f[i][j],f[i-1][j-v[i]-v[attatch[i][1]]-v[attatch[i][0]]]+
(v[i]*w[i]+v[attatch[i][1]]*w[attatch[i][1]]+v[attatch[i][0]]*w[attatch[i][0]]));
}
}
}
}
int ans=0;
for(int i=0;i<=n;i++){
ans=max(ans,f[m][i]);
}
cout<<ans<<endl;
return 0;
}
为什么不对啊 !!!!!!!