NOIP 2006 tg T2金明的预算方案

本文主要是介绍NOIP 2006 tg T2金明的预算方案，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://www.luogu.org/problem/show?pid=1064#
麻烦一点的背包DP，其实还是01背包，因为只可能有0,1,2件附件，都比一比就行了。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int m,n,k,W,V,f[33000],w[100][10],v[100][10],p,num[100],id[100];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&W,&V,&p);
        if(p==0)
        {
            k++;
            w[k][0]=W;
            v[k][0]=V*W;
            id[i]=k;
            num[k]++;
        }
        else
        {
            w[id[p]][num[id[p]]]=W;
            v[id[p]][num[id[p]]]=V*W;
            num[id[p]]++;
        }
    } 
    for(int i=1;i<=k;i++)
    {
        for(int j=n;j>=10;j-=10)
        {
            if(j-w[i][0]>=0)
            f[j]=max(f[j],f[j-w[i][0]]+v[i][0]);
            if(j-w[i][0]-w[i][1]>=0)
            f[j]=max(f[j],f[j-w[i][0]-w[i][1]]+v[i][0]+v[i][1]);
            if(j-w[i][0]-w[i][2]>=0)
            f[j]=max(f[j],f[j-w[i][0]-w[i][2]]+v[i][0]+v[i][2]);
            if(j-w[i][0]-w[i][1]-w[i][2]>=0)
            f[j]=max(f[j],f[j-w[i][0]-w[i][1]-w[i][2]]+v[i][0]+v[i][1]+v[i][2]);
        }
    }
    printf("%d",f[n]);
    return 0;
}

这篇关于NOIP 2006 tg T2金明的预算方案的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---