WA #3 求看

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

Harry_hcx @ 2021-07-01 13:28:57

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct item{
    int value,importance;
};
vector<item>itm[62];
int num,n,m,f[32004],ai[302][10],av[320][10];
int main(){
    cin>>m>>num;
    for (int i=1;i<=num;i++){
        int v,p,q;
        cin>>v>>p>>q;
        item wait;
        wait.value=v;
        wait.importance=p;
        if (q==0){
            itm[i].push_back(wait);
        }
        else{
            itm[q].push_back(wait);
        }
    }
    for (int i=1;i<=num;i++){
        if (itm[i].capacity()==1){
            av[i][1]=itm[i][0].value;
            ai[i][1]=itm[i][0].importance*itm[i][0].value;
        }
        else if (itm[i].size()==2){
            av[i][1]=itm[i][0].value;
            ai[i][1]=itm[i][0].importance*itm[i][0].value;
            av[i][2]=itm[i][0].value+itm[i][1].value;
            ai[i][2]=ai[i][1]+itm[i][1].importance*itm[i][1].value;
        }
        else if (itm[i].size()==3){
            av[i][1]=itm[i][0].value;
            ai[i][1]=itm[i][0].importance*itm[i][0].value;
            av[i][2]=itm[i][0].value+itm[i][1].value;
            ai[i][2]=ai[i][1]+itm[i][1].importance*itm[i][1].value;
            av[i][3]=itm[i][0].value+itm[i][2].value;
            ai[i][3]=ai[i][1]+itm[i][2].importance*itm[i][2].value;
            av[i][4]=itm[i][0].value+itm[i][1].value+itm[i][2].value;
            ai[i][4]=ai[i][2]+itm[i][2].importance*itm[i][2].value;
        }
        else continue;
    }
    memset(f,-1,sizeof(f));
    f[0]=0;
    for (int i=1;i<=num;i++)
        for (int j=m;j>=0;j--)
            for (int k=1;k<=4;k++)
                if (j+av[i][k]<=m&&f[j]!=-1)
                    f[j+av[i][k]]=max(f[j]+ai[i][k],f[j]);
    int ans=0;
    for (int i=1;i<=m;i++)
        ans=max(ans,f[i]);
    cout<<ans;
    return 0;
}

答案7430 我的7400
2000 10
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5


by _l_l_l_l_l_ @ 2021-07-06 19:04:00

谢谢白送的数据


|