http://www.vijos.cn/Problem_Show.asp?id=1313
#include<iostream>
using namespace std;
struct Node
{
    int v;//該物品的價格
    int p;//該物品的重要度
    int mark;//標記該物品是否為主件,mark=0表示為主件,否則表示其主件號
    int fj1;//附件1 * fj1 = 0 表示沒有附件1，否則為附件號
    int fj2;//附件2 * fj2 = 0 表示沒有附件2，否則為附件號
}; 
int MAX(int x,int y)
{
    if(x>y)
        return x;
    else
        return y;
}
int main()
{
    int N,m;//N 錢數，m 物品數量
    while(cin>>N>>m)
    {
        int i,j,temp,p1,p2;
        int dp[32001];
        Node obj[60];
        for(i=1;i<=m;i++) //開始都沒有附件
            obj[i].fj1 = obj[i].fj2 = 0;

        for(i=1;i<=m;i++)
        {            
            scanf("%d%d%d",&obj[i].v,&obj[i].p,&obj[i].mark);            
            if(obj[i].mark != 0) //不是主件 就要找其主件
            {
                if(obj[obj[i].mark].fj1 != 0)
                {
                    if(obj[obj[obj[i].mark].fj1].v > obj[i].v)//保證附件1的價格要小
                    {
                        temp = obj[obj[i].mark].fj1;
                        obj[obj[i].mark].fj1 = i;
                        obj[obj[i].mark].fj2 = temp;
                    }
                    else 
                        obj[obj[i].mark].fj2 = i;
                }
                else 
                    obj[obj[i].mark].fj1 = i;
            }
        }
        if(obj[1].mark == 0)
        {
            if(obj[1].fj1 == 0 && obj[1].fj2 == 0)
            {
                for(j=0;j<obj[1].v;j++)
                    dp[j] = 0;
                for(;j<=N;j++)
                    dp[j] = obj[1].v * obj[1].p;
            }
            else if(obj[1].fj1 != 0 && obj[1].fj2 == 0)
            {
                p1 = obj[1].fj1;
                for(j=0;j<obj[1].v;j++)//什么都不能買
                    dp[j] = 0;
                for(;j<obj[1].v + obj[p1].v ;j++)//只能買主件
                    dp[j] = obj[1].v * obj[1].p;
                for(;j<=N;j++)
                    dp[j] = obj[1].v * obj[1].p + obj[p1].v * obj[p1].p;
            } 
            else
            {
                p1 = obj[1].fj1;
                p2 = obj[1].fj2;
                for(j=0;j<obj[1].v;j++)//什么都不能買
                    dp[j] = 0;

                for(;j<obj[1].v + obj[p1].v ;j++) //只能買主件
                    dp[j] = obj[1].v*obj[1].p;

                for(;j<obj[1].v + obj[p2].v ;j++) //能買主件與附件1
                    dp[j] = obj[1].v*obj[1].p + obj[p1].v*obj[p1].p;

                for(;j<obj[1].v + obj[p1].v + obj[p2].v ;j++) //能買主件與一個附件
                    dp[j] = MAX(obj[1].v*obj[1].p + obj[p1].v*obj[p1].p,obj[1].v*obj[1].p + obj[p2].v*obj[p2].p);

                for(;j<=N;j++) //都能買
                    dp[j] = obj[1].v*obj[1].p + obj[p1].v*obj[p1].p + obj[p2].v*obj[p2].p;
            }
        }//if(obj[1].mark == 0)
        else //第1件物品是附件
        {
            for(j=0;j<=N;j++)
                dp[j] = 0;
        }
        
        for(i=2;i<=m;i++)
        {
            if(obj[i].mark == 0)//第i件物品是主件
            {
                if(obj[i].fj1 == 0 && obj[i].fj2 == 0) //沒有附件
                {
                    //只夠買主件
                    for(j=N;j>=obj[i].v;j--)
                        dp[j] = MAX(dp[j],dp[j-obj[i].v] + obj[i].v*obj[i].p);
                }
                else if(obj[i].fj1 != 0 && obj[i].fj2 == 0) //有附件1
                {
                    p1 = obj[i].fj1;
                    for(j=N;j>=obj[i].v + obj[p1].v;j--)
                    {
                        temp = dp[j];
                        //買主件與附件1
                        if(temp < dp[j-obj[i].v-obj[p1].v] + obj[i].v*obj[i].p + obj[p1].v*obj[p1].p)
                            temp = dp[j-obj[i].v-obj[p1].v] + obj[i].v*obj[i].p + obj[p1].v*obj[p1].p;
                        //只買主件
                        if(temp < dp[j-obj[i].v ] + obj[i].v*obj[i].p)
                            temp = dp[j-obj[i].v ] + obj[i].v*obj[i].p;
                        dp[j] =temp;
                    }
                    //只夠買主件
                    for(;j>=obj[i].v;j--)
                        dp[j] = MAX(dp[j],dp[j-obj[i].v] + obj[i].v*obj[i].p);
                }
                else //有兩個附件
                {
                    p1 = obj[i].fj1;
                    p2 = obj[i].fj2;

                     for(j=N;j>=obj[i].v + obj[p1].v + obj[p2].v;j--)
                    {
                        temp = dp[j];
                        //主件與兩附件都買
                        if(temp < dp[j-obj[i].v-obj[p1].v-obj[p2].v] + obj[i].v*obj[i].p + obj[p1].v*obj[p1].p + obj[p2].v*obj[p2].p)
                            temp = dp[j-obj[i].v-obj[p1].v-obj[p2].v] + obj[i].v*obj[i].p + obj[p1].v*obj[p1].p + obj[p2].v*obj[p2].p;
                        //買主件與附件2
                        if(temp < dp[j-obj[i].v-obj[p2].v] + obj[i].v*obj[i].p + obj[p2].v*obj[p2].p)
                            temp = dp[j-obj[i].v-obj[p2].v] + obj[i].v*obj[i].p + obj[p2].v*obj[p2].p;
                        //買主件與附件1
                        if(temp < dp[j-obj[i].v-obj[p1].v] + obj[i].v*obj[i].p + obj[p1].v*obj[p1].p)
                            temp = dp[j-obj[i].v-obj[p1].v] + obj[i].v*obj[i].p + obj[p1].v*obj[p1].p;
                        //只買主件
                        if(temp < dp[j-obj[i].v ] + obj[i].v*obj[i].p)
                            temp = dp[j-obj[i].v ] + obj[i].v*obj[i].p;
                        dp[j] = temp;
                    }
                    for(;j>=obj[i].v + obj[p2].v;j--)
                    {
                        temp = dp[j];
                        //買主件與附件2
                        if(temp < dp[j-obj[i].v-obj[p2].v] + obj[i].v*obj[i].p + obj[p2].v*obj[p2].p)
                            temp = dp[j-obj[i].v-obj[p2].v] + obj[i].v*obj[i].p + obj[p2].v*obj[p2].p;
                        //買主件與附件1
                        if(temp < dp[j-obj[i].v-obj[p1].v] + obj[i].v*obj[i].p + obj[p1].v*obj[p1].p)
                            temp = dp[j-obj[i].v-obj[p1].v] + obj[i].v*obj[i].p + obj[p1].v*obj[p1].p;
                        //只買主件
                        if(temp < dp[j-obj[i].v ] + obj[i].v*obj[i].p)
                            temp = dp[j-obj[i].v ] + obj[i].v*obj[i].p;
                        dp[j] = temp;
                    }
                    for(;j>=obj[i].v + obj[p1].v;j--)
                    {
                        temp = dp[j];
                        //買主件與附件1
                        if(temp < dp[j-obj[i].v-obj[p1].v] + obj[i].v*obj[i].p + obj[p1].v*obj[p1].p)
                            temp = dp[j-obj[i].v-obj[p1].v] + obj[i].v*obj[i].p + obj[p1].v*obj[p1].p;
                        //只買主件
                        if(temp < dp[j-obj[i].v ] + obj[i].v*obj[i].p)
                            temp = dp[j-obj[i].v ] + obj[i].v*obj[i].p;
                        dp[j] = temp;
                    }
                    //只夠買主件
                    for(;j>=obj[i].v;j--)
                        dp[j] = MAX(dp[j],dp[j-obj[i].v] + obj[i].v*obj[i].p);            
                }
            }
        }
        cout<<dp[N]<<endl;
    }
    return 0;
}

/*
4500 12 
100 3 0 
400 5 0 
300 5 0
1400 2 0 
500 2 0 
800 2 4
1400 5 4 
300 5 0
1400 3 8 
500 2 0
1800 4 0
440 5 10
1000   5   
300　　 5   0   
400　　 2   0   
300　　 5   2   
300　　 4   2   
600　　 4   0
*/