金明的预算方案

又是一个当初没学会的dp模型.也就是分组背包...

#include <bits/stdc++.h>
using namespace std;
const int N=65,M=4e4;
struct vv{
    int price,val,team;
}a[N];
int f[M],g[M];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].price,&a[i].val,&a[i].team);
        a[i].val*=a[i].price;
    }
    for(int i=1;i<=m;i++)
    {
        if(!a[i].team)//说明是主件.
        {
            //更新信息.
            for(int j=1;j<=a[i].price;j++)  g[j]=0;
            for(int j=a[i].price;j<=n;j++)  g[j]=f[j-a[i].price]+a[i].val;
            for(int j=1;j<=m;j++)
            {
                if(a[j].team==i)
                {
                    for(int k=n;k>=a[i].price+a[j].price;k--)
                        g[k]=max(g[k-a[j].price]+a[j].val,g[k]);
                }
            }
            for(int j=a[i].price;j<=n;j++) f[j]=max(f[j],g[j]);
        }
    }
    printf("%d\n",f[n]);
    return 0;
}