題目大意：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 <stdio.h>
#include <string.h>
#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
