AreYouBusy
【题目链接】AreYouBusy
【题目类型】分组背包
&题意:
给你n个工作集合,给你T的时间去做它们。给你m和s,说明这个工作集合有m件事可以做,它们是s类的工作集合(s=0,1,2,s=0说明这m件事中最少得做一件,s=1说明这m件事中最多只能做一件,s=2说明这m件事你可以做也可以不做)。再给你ci和gi代表你做这件事要用ci的时间,能获得gi的快乐值。求在T的时间内你能获得的最大快乐值。
&题解:
s等于1是分组 2是01背包 等于0时有点难,是分组背包变形,还不是很懂
&代码:
#include <cstdio>
#include <bitset>
#include <iostream>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define fo(i,a,b) for(int i=(a);i<=(b);i++)
#define fd(i,a,b) for(int i=(a);i>=(b);i--)
const int maxn = 1e2 + 7;
int n, t, dp[maxn][maxn], C[maxn], W[maxn];
int main() {
freopen("E:1.in", "r", stdin);
while(cin >> n >> t) {
memset(dp, 0, sizeof(dp));
int m, s;
fo(i, 1, n) {
cin >> m >> s;
fo(i, 1, m) cin >> C[i] >> W[i];
if(s == 0) {
fo(j, 0, t) dp[i][j] = -INF;
fo(k, 1, m) {
fd(j, t, C[k]) {
dp[i][j] = max(dp[i][j], dp[i][j - C[k]] + W[k]);
dp[i][j] = max(dp[i][j], dp[i - 1][j - C[k]] + W[k]);
//为什么把这2个分开求会wa? 必须一起求才会a?
}
}
// fo(k, 1, m) {
// fd(j, t, C[k]) {
// }
// }
}
else if(s == 1) {
//这块必须要赋值为上一层,因为上一层可能是-INF,如果不赋值 就不能传递下去了
fo(j, 0, t) dp[i][j] = dp[i - 1][j];
fo(k, 1, m) {
fd(j, t, C[k]) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - C[k]] + W[k]);
}
}
}
else {
fo(j, 0, t) dp[i][j] = dp[i - 1][j];
fo(k, 1, m) {
fd(j, t, C[k]) {
dp[i][j] = max(dp[i][j], dp[i][j - C[k]] + W[k]);
}
}
}
}
cout << max(dp[n][t], -1) << endl;
}
return 0;
}