最弱求助30分qwq

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

hegongda307 @ 2019-12-06 22:42:24

//#include<iostream>
#include<cstdio>
#define maxn 32001
using namespace std;
int max(int a,int b) {return a>b?a:b;}
int n,m;
int v,p,q;
int mw[maxn];
int mc[maxn];
int aw[maxn][3];
int ac[maxn][3];
int f[maxn];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&v,&p,&q);
        //printf("%d %d %d\n",v,p,q);
        if(!q)//主件
        {
            mw[i]=v;//价格是v
            mc[i]=v*p;//价值是v*p
        }
        else{//附件
            aw[q][0]++;
            aw[q][aw[q][0]]=v;//价格
            ac[q][ac[q][0]]=v*p;//价值
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=n;mw[i]!=0&&j>=mw[i];j--)
        {
            f[j]=max(f[j],f[j-mw[i]]+mc[i]);
            if(j>=mw[i]+aw[i][1]) f[j]=max(f[j],f[j-mw[i]-aw[i][1]]+mc[i]+ac[i][1]);
            if(j>=mw[i]+aw[i][2]) f[j]=max(f[j],f[j-mw[i]-aw[i][2]]+mc[i]+ac[i][2]);
            if(j>=mw[i]+aw[i][1]+aw[i][2]) f[j]=max(f[j],f[j-mw[i]-aw[i][1]-aw[i][2]]+mc[i]+ac[i][1]+ac[i][2]);
        }
    }
    printf("%d\n",f[n]);
    return 0;
}

by Canony @ 2019-12-10 20:06:50

ac[q][ac[q][0]]=v*p; 里面应该是aw


|