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

题意： 多组背包， 0类型为为至少去1样， 1为至多取1样， 2 为随意。

如果将2类型 再添加一组数据 （0， 0）， 则可转换为0类型， 即0,1 背包问题， 1类型为经典分组背包。

/***Good Luck***/
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include
#include

#define Zero(a) memset(a, 0, sizeof(a))
#define Neg(a) memset(a, -1, sizeof(a))
#define All(a) a.begin(), a.end()
#define PB push_back
#define inf 0x3f3f3f3f
#define inf2 0x7fffffffffffffff
#define ll long long
using namespace std;
//#pragma comment(linker, "/STACK:102400000,102400000")
void get_val(int &a) {
int value = , s = ;
char c;
while ((c = getchar()) == ' ' || c == '\n');
if (c == '-') s = -s; else value = c - ;
while ((c = getchar()) >= '' && c <= '')
value = value * + c - ;
a = s * value;
}
const int maxn = ;
int n, t;
int dp[maxn][maxn];
int C[maxn][maxn];
int G[maxn][maxn];
int TE[maxn];
int N1[maxn];

int main() {
//freopen("data.out", "w", stdout);
//freopen("data.in", "r", stdin);
//cin.sync_with_stdio(false);
while (cin >> n >> t){
for (int i = ; i < maxn; ++i) for (int j = ; j < maxn; ++j) dp[i][j] = -inf; Zero(dp[]); int n1, te; for (int i = ; i <= n; ++i) { scanf("%d%d", &n1, &te); for (int j = ; j <= n1; ++j) { scanf("%d%d", C[i] + j, G[i] + j); } if (te != ) {// 情况一和情况三相似， 在情况三中添加一组0， 0 便可表示任意取 n1++; // 及可取可不取。 C[i][n1] = ; G[i][n1] = ; } TE[i] = te; N1[i] = n1; } for (int i = ; i <= n; ++i) { if (TE[i] == ) { for (int ii = ; ii <= N1[i]; ++ii) //dp[i][v] = max(dp[i][v], dp[i][v - C[i][ii]] + G[i][ii],dp[i - 1][v - C[i][ii]] + G[i][ii]) for (int v = t; v >= C[i][ii]; --v) {
dp[i][v] = max(dp[i][v], dp[i][v - C[i][ii]] + G[i][ii]);
dp[i][v] = max(dp[i][v], dp[i - ][v - C[i][ii]] + G[i][ii]);
}
}
else if (TE[i] == ) {
for (int v = t; v >= ; v--)
for (int ii = ; ii <= N1[i]; ++ii) if (v >= C[i][ii])
dp[i][v] = max(dp[i][v], dp[i - ][v - C[i][ii]] + G[i][ii]);
}
else {
for (int ii = ; ii <= N1[i]; ++ii) for (int v = t; v >= C[i][ii]; --v) {
dp[i][v] = max(dp[i][v], dp[i][v - C[i][ii]] + G[i][ii]);
dp[i][v] = max(dp[i][v], dp[i - ][v - C[i][ii]] + G[i][ii]);
}
}
}
if (dp[n][t] >= )
printf("%d\n", dp[n][t]);
else printf("-1\n");
}
return ;
}