学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3535

这个题目本来是不难的，但是众多背包问题混合到一起就感觉不好做了，如果分开那么都会做

想解这个问题一定要理解各种类型的背包问题才行！

s=0这个是一个每组至少选一个的背包，首先这组初始化为-1，最后从上一个和本数组不为-1的位置选，如果某个位置为-1，那么说明这个位置对于前面

背包分组的要求就不满足

s=1这个就是规矩的分组背包

s=2的时候直接0-1背包

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define MAX(a,b) (a>b?a:b)
int dp[10000][110];
int n,m,t,s;
int main(){
    int i,j,k,v,c,p,q,r;
    while(scanf("%d%d",&n,&t)!=EOF){
        memset(dp,-1,sizeof(dp));
        for(i=0;i<110;i++) dp[0][i]=0;
        k=1;
        for(i=0;i<n;i++){
            scanf("%d%d",&m,&s);
            if(s==0){
                for(j=0;j<m;j++){
                    scanf("%d%d",&v,&c);
                    for(p=t;p>=v;p--){
                        if(dp[k][p-v]!=-1) dp[k][p]=MAX(dp[k][p],dp[k][p-v]+c);
                        if(dp[k-1][p-v]!=-1) dp[k][p]=MAX(dp[k][p],dp[k-1][p-v]+c);
                    }
                }
            }
            else if(s==1){
                for(j=0;j<=t;j++) dp[k][j]=dp[k-1][j];
                for(j=0;j<m;j++){
                    scanf("%d%d",&v,&c);
                    for(p=t;p>=v;p--)
                    if(dp[k-1][p-v]!=-1)dp[k][p]=MAX(dp[k][p],dp[k-1][p-v]+c);
                }
            }
            else{
                for(j=0;j<=t;j++) dp[k][j]=dp[k-1][j];
                for(j=0;j<m;j++){
                    scanf("%d%d",&v,&c);
                    for(p=t;p>=v;p--){
                        if(dp[k][p-v]!=-1) dp[k][p]=MAX(dp[k][p],dp[k][p-v]+c);
                    }
                }
            }
            k++;
        }
        printf("%d\n",dp[k-1][t]);
    }
    return 0;
}