记录编号	286831	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	Twist Fate	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2016-08-01 09:30:57	内存使用	0.48 MiB

//经典的有依赖背包问题~~~~~ 
//这种题目的方法就是分类讨论，
//首先假设只选主件，那么不就是一个简单的01背包吗？o(>﹏<)o
//然后考虑选第一件附件，同上，只要在数组中多减一个附件就好了
// 然后选第二件。。。烦死了/(ㄒoㄒ)/~~
//最后就是同时选两件。。。一样，在f【】中同时减去两件的价格即可
//这样就大功告成了O(∩_∩)O~~ 
#include<cstdio> 
#include<algorithm>
using namespace std;
int w[70],p[70],q[70],f[50000]; //w表示价格，p表示重要度，q表示主见还是附件   
int main()  
{  
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
    int n,m;     
    int l=0;  
    scanf("%d%d",&n,&m);  
    for(int i=1;i<=m;i++)  
    {  
        scanf("%d%d%d",&w[i],&p[i],&q[i]);  
    }  
    for(int i=1;i<=m;i++)  
    {  
        int k1=0;  
        int k2=0;  
        int t1=0;  
        int t2=0;  
        if(q[i]==0)  
        {  
            for(int k=i+1;k<=m;k++)  
                if(q[k]==i)                         
                {  
                    t1=k;  
                    k1=1;  
                    break;  
                }  
                for(int k=t1+1;k<=m;k++)  
                    if(q[k]==i)                         
                    {  
                        t2=k;  
                        k2=1;  
                        break;  
                    }   
                    for(int j=n;j>=w[i];j--)  
                    {         
                        f[j]=max(f[j-w[i]]+w[i]*p[i],f[j]);  
                        f[j]=max(f[j-w[i]]+w[i]*p[i],f[j]);     
                        if((j-w[i]-w[t1])>=0&&k1==1)                           
							f[j]=max(f[j-w[i]-w[t1]]+w[i]*p[i]+w[t1]*p[t1],f[j]);  
                        if((j-w[i]-w[t2])>=0&&k2==1)                                             
                            f[j]=max(f[j-w[i]-w[t2]]+w[i]*p[i]+w[t2]*p[t2],f[j]);  
                        if((j-w[i]-w[t1]-w[t2])>=0&&k1==1&&k2==1)                                             
                            f[j]=max(f[j-w[i]-w[t1]-w[t2]]+w[i]*p[i]+w[t1]*p[t1]+w[t2]*p[t2],f[j]);           
                    }  
        }  
    }  
    printf("%d\n",f[n]);  
    return 0;  
}