为什么不对啊

P1064 [NOIP2006 提高组] 金明的预算方案

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;
}

为什么不对啊 !!!!!!!


|