金明的预算方案 （C++代码）

解题思路:





注意事项:





参考代码:

#include <iostream>

#include <cstdio>

#include <stdio.h>

#include <algorithm>

#include <vector>

#define pb push_back

using namespace std;

int feesum,n,ans,f[33000],cnt,num[65];

struct node{int w,v,is;}t[65];

vector<int>goods[65];

bool cmp(node x,node y){return x.is<y.is;}

int main(){

    scanf("%d%d",&feesum,&n);

    for(int i=1;i<=n;i++){

        int x,y,z;scanf("%d%d%d",&x,&y,&z);

        t[i].w=x;t[i].v=y;t[i].is=z;

    }

    //sort(t+1,t+1+n,cmp);这句话是完全没必要的，结果一开始我加了这句排序的语句还WA了6个点

    for(int i=1;i<=n;i++){

        if(!t[i].is){goods[i].pb(i);num[++cnt]=i;}//将主物品存下来，主物品的编号放到另一个数组里，枚举时节约时间

        else goods[t[i].is].pb(i);//附属品存下来

    }

    for(int i=cnt;i>=1;i--)//枚举下标，但是要取其中的值

        for(int j=feesum;j>=t[num[i]].w;j-=10){//因为是十的倍数直接-=10跑得更快

            int pos=num[i];int len=goods[pos].size();

            f[j]=max(f[j],f[j-t[pos].w]+t[pos].v*t[pos].w);

            if(len>=2&&j-t[pos].w-t[goods[pos][1]].w>=0)f[j]=max(f[j],f[j-t[pos].w-t[goods[pos][1]].w]+t[pos].v*t[pos].w+t[goods[pos][1]].v*t[goods[pos][1]].w);

            if(len>=3&&j-t[pos].w-t[goods[pos][1]].w-t[goods[pos][2]].w>=0)f[j]=max(f[j],f[j-t[pos].w-t[goods[pos][1]].w-t[goods[pos][2]].w]+t[pos].v*t[pos].w+t[goods[pos][1]].v*t[goods[pos][1]].w+t[goods[pos][2]].v*t[goods[pos][2]].w);

            if(len>=4&&j-t[pos].w-t[goods[pos][1]].w-t[goods[pos][2]].w-t[goods[pos][3]].w>=0)f[j]=max(f[j],f[j-t[pos].w-t[goods[pos][1]].w-t[goods[pos][2]].w-t[goods[pos][3]].w]+t[pos].v*t[pos].w+t[goods[pos][1]].v*t[goods[pos][1]].w+t[goods[pos][2]].v*t[goods[pos][2]].w+t[goods[pos][3]].v*t[goods[pos][3]].w);//四个状态转移方程

            ans=max(f[j],ans);//记录答案

        }

    printf("%d",ans);

    return 0;

}