题目大意：xiaoA想尽量多花时间做ACM，但老板要求他在t时间内做完n堆工作，每个工作耗时cost[i][j]，幸福感val[i][j]，每个工作有num[i]个工作，每堆工作都有一个性质，0表示至少要做里面的1个工作，1表示最多做里面的1个工作，2表示随意，做或不做都行。最后问在符合老板要求的情况下的最大幸福感，怎么都不符合要求就输出-1.

解题思路：这是混合背包吗？尼玛的这样混合我的状态转移方程都没办法写了。
可以把每堆工作当做一个组，然后每个组有自己的状态转移方程;
当某组的性质为0时是分组背包变形，每次状态从前一组获当前组转移而来，能从一个地方转移而来，这组就合法。
当某组的性质为1时，就是分组背包，但这里是用二维数组，在一组计算完成之后，要把前一组的结果复制下来。
当某组的性质为2时，就把这组当成01背包来做，也要记得把前一组的结果复制下来，因为本组可以不选。
本题有个trick，那就是容量是从0开始的，和常规的容量从1开始不一样，要注意for循环里的下界。

测试数据：
1 0
2 0
0 1
0 2

1 0
2 2
0 1
0 2

1 1000
2 0
1 1
2 2

代码：
[cpp]
#include
#include
#define MAX 102
#define max(a,b) (a) > (b) (a) : (b)


int ans,dp[MAX][MAX];
int n,m,num[MAX],flag[MAX];
int cost[MAX][MAX],val[MAX][MAX];


int Solve_1A() {

int i,j,k,tpval;


dp[0][0] = 0;
for (i = 1; i <= n; ++i) {

if (flag[i] == 2) {
//01背包 www.2cto.com
for (k = 1; k <= num[i]; ++k)
for (j = m; j >= cost[i][k]; --j) {

tpval = dp[i][j-cost[i][k]];
if ( tpval != -1) dp[i][j] = max(dp[i][j],tpval+val[i][k]);
tpval = dp[i-1][j-cost[i][k]];
if ( tpval != -1) dp[i][j] = max(dp[i][j],tpval+val[i][k]);

}
for (j = 0; j <= m; ++j)
dp[i][j] = max(dp[i][j],dp[i-1][j]);
}
else if (flag[i] == 1) {
//分组背包，最多选一个,保证dp[i][j]只由上一次的一个状态转移而来
for (j = m; j >= 0; --j)
for (k = 1; k <= num[i]; ++k)
if (j >= cost[i][k]) {

tpval = dp[i-1][j-cost[i][k]];
if (tpval != -1) dp[i][j] = max(dp[i][j],tpval+val[i][k]);
}
for (j = 0; j <= m; ++j)
dp[i][j] = max(dp[i][j],dp[i-1][j]);
}
else {
//至少选一个的分组背包
for (k = 1; k <= num[i]; ++k)
for (j = m; j >= cost[i][k]; --j) {

tpval = dp[i][j-cost[i][k]];
if (tpval != -1)
dp[i][j] = max(dp[i][j],tpval+val[i][k]);
tpval = dp[i-1][j-cost[i][k]];
if (tpval != -1)
dp[i][j] = max(dp[i][j],tpval+val[i][k]);

}
}

//本组不合法，可直接返回-1
for (j = 0; j <= m; ++j)
if (dp[i][j] != -1) break;
if (j == m + 1) return -1;
}


for (ans = -1,i = 0; i <= m; ++i)
ans = max(ans,dp[n][i]);
return ans;
}


int main()
{
int i,j,k,t,tpval;


while (scanf("%d%d",&n,&m) != EOF) {

memset(dp,-1,sizeof(dp));
memset(num,0,sizeof(num));
for (i = 1; i <= n; ++i) {

scanf("%d%d",&num[i],&flag[i]);
for (j = 1; j <= num[i]; ++j)
scanf("%d%d",&cost[i][j],&val[i][j]);
}


int ans = Solve_1A();
printf("%d\n",ans);
}
}

摘自 ZeroClock