Hdu 3535 AreYouBusy(DP_背包)
题目大意：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