50分求dalao帮助。。不知道错哪里。。

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

魔塔哈奇 @ 2017-09-29 20:30:07

#include <bits/stdc++.h>
using namespace std;
int n, m;
int v[70], p[70], q[70], imp[70], bp[32010];
int main(){
    cin>> n>> m;
    for(int i=1; i<=m; i++){
        cin>> v[i]>> p[i]>> q[i];
        imp[i]=v[i]*p[i];
    }
    memset(bp, 0, sizeof(bp));
    for(int i=1; i<=m; i++)
    {
        if(q[i]!=0) continue;
        for(int j=n; j>=v[i]; j--)
        {
            if(bp[j-v[i]]+imp[i]>bp[j]) //比较放主件与不放 
            {
                bp[j]=bp[j-v[i]]+imp[i]; 
                int tmp[2], now=0;
                for(int k=1; k<=m; k++)
                {
                    if(q[k]!=i) continue;
                    if(j<v[k]+v[i]) continue;
                    tmp[now++]=k;
                    if(now==2) break;
                }
                if(now>0)
                    bp[j]=max(bp[j-v[i]-v[tmp[0]]]+imp[i]+imp[tmp[0]], bp[j]); //比较放第一个附件和不放附件 
                if(now>1){
                    bp[j]=max(bp[j-v[i]-v[tmp[1]]]+imp[i]+imp[tmp[1]], bp[j]); //比较放第二个附件和不放附件 
                    if(j>=v[i]+v[tmp[0]]+v[tmp[1]])
                        bp[j]=max(bp[j-v[i]-v[tmp[0]]-v[tmp[1]]]+imp[i]+imp[tmp[0]]+imp[tmp[1]], bp[j]); // 比较放第一个和第二个附件和不放附件 
                }    
            }
        }
    }
    cout<< bp[n];
    return 0;
}

|