hdu 3535 AreYouBusyミックスリュックサック

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=3535
3つの任務があって、少なくとも1つを完成して、せいぜい1つを完成して、任意に完成します.次に、kグループのタスクが与えられ、各グループのタスクは3つのタスクの1つに属する.それぞれのタスクは時間を費やし、幸福感を得る.時間T内の最大の満足感を求めます.
3種類のリュックサックのミックス.やはりリュックサック問題に対する理解を考察する.明らかに1次元は要求を満たすことができず,d[k][j]はk番目のグループ容量がjである場合に得られる最大満足感を表すとする.
3種類のリュックサックの違いを明らかに比較することができます.(任意に取ったのが01バックパック)
任意に取り、少なくとも1つの違いを取ります:1つの状態だけを取るのは不法ですか.
任意に取り、最大1つの違いを取ります:現在のグループがすでに取った場合に取り続けるかどうか.

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define N 110
using namespace std;

int d[N][N];

int main()
{
    int n,m,s,T,c,w;
    while(~scanf("%d%d",&n,&T))
    {
        memset(d,0,sizeof(d));
        for(int k=1;k<=n;k++)
        {
            cin>>m>>s;
            for(int j=0;j<=T;j++)   d[k][j]=(s==0?-1:d[k-1][j]);
            //    k      。s=0   ，  -1。     ，         。
            for(int i=0;i<m;i++)
            {
                scanf("%d%d",&c,&w);
                if(s==0)
                    for(int j=T;j>=c;j--)
                    {
                        if(d[k][j-c]!=-1)   d[k][j]=max(d[k][j],d[k][j-c]+w);
                        if(d[k-1][j-c]!=-1) d[k][j]=max(d[k][j],d[k-1][j-c]+w);//    
                    }
                if(s==1)
                    for(int j=T;j>=c;j--)
                        if(d[k-1][j-c]!=-1)  d[k][j]=max(d[k][j],d[k-1][j-c]+w);
                if(s==2)
                    for(int j=T;j>=c;j--)
                    {
                        if(d[k][j-c]!=-1)    d[k][j]=max(d[k][j],d[k][j-c]+w);
                        if(d[k-1][j-c]!=-1)  d[k][j]=max(d[k][j],d[k-1][j-c]+w);
                    }
            }
        }
        cout<<d[n][T]<<endl;
    }
}