背包DP——混合背包
顾名思义,混合背包就是将前面三种的背包问题(01,完全,多重)混合起来,有的只能取一次,有的能取无限次,有的只能取 k 次。
正解
特解
部分情况下,如小数据,可以转换成多重背包(把完全情况的数量换成足够大,如1e7,就把完全相对变成了多重)
例题
https://www.luogu.com.cn/problem/P1833
樱花
题目背景
《爱与愁的故事第四弹·plant》第一章。
题目描述
爱与愁大神后院里种了 \(n\) 棵樱花树,每棵都有美学值 \(C_i(0 \le C_i \le 200)\)。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸,他懂得如何欣赏樱花:一种樱花树看一遍过,一种樱花树最多看 \(P_i(0 \le P_i \le 100)\) 遍,一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 \(T_i(0 \le T_i \le 100)\)。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时(或提早)去上学。
输入格式
共 \(n+1\)行:
第 \(1\) 行:现在时间 \(T_s\)(几时:几分),去上学的时间 \(T_e\)(几时:几分),爱与愁大神院子里有几棵樱花树 \(n\)。这里的 \(T_s\),\(T_e\) 格式为:hh:mm
,其中 \(0 \leq hh \leq 23\),\(0 \leq mm \leq 59\),且 \(hh,mm,n\) 均为正整数。
第 \(2\) 行到第 \(n+1\) 行,每行三个正整数:看完第 \(i\) 棵树的耗费时间 \(T_i\),第 \(i\) 棵树的美学值 \(C_i\),看第 \(i\) 棵树的次数 \(P_i\)(\(P_i=0\) 表示无数次,\(P_i\) 是其他数字表示最多可看的次数 \(P_i\))。
输出格式
只有一个整数,表示最大美学值。
样例 #1
样例输入 #1
6:50 7:00 3
2 1 0
3 3 1
4 5 4
样例输出 #1
11
提示
\(100\%\) 数据:\(T_e-T_s \leq 1000\)(即开始时间距离结束时间不超过 \(1000\) 分钟),\(n \leq 10000\)。保证 \(T_e,T_s\) 为同一天内的时间。
样例解释:赏第一棵樱花树一次,赏第三棵樱花树 \(2\) 次。
Code
点击查看代码
const int maxn = 1e7 + 10;
int dp[maxn], w[maxn], v[maxn], sum[maxn];
int wnew[maxn], vnew[maxn];
pair<int, int> huan(string s) {
int h, t;
h = s[0] - '0';
if (s.size() == 5) {
h = h * 10 + s[1] - '0';
t = (s[3] - '0') * 10 + s[4] - '0';
}
else { t = (s[2] - '0') * 10 + s[3] - '0'; }
pair<int, int> p;
p = {h, t};
return p;
}
void solve() {
int n, m;
string s1, s2;
cin >> s1 >> s2 >> n;
auto [a1, b1] = huan(s1);
auto [a2, b2] = huan(s2);
m = (a2 - a1) * 60 + b2 - b1;
int cnt = 0;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i] >> sum[i];
int x = sum[i], j = 1;
if (x == 0) x = maxn;
while (x) {
if (j <= x) {
x -= j;
wnew[++cnt] = w[i] * j;
vnew[cnt] = v[i] * j;
j <<= 1;
}
else {
wnew[++cnt] = w[i] * x;
vnew[cnt] = v[i] * x;
break;
}
}
}
for (int i = 1; i <= cnt; i++) {
for (int j = m; j >= wnew[i]; j--) {
dp[j] = max(dp[j], dp[j - wnew[i]] + vnew[i]);
}
}
cout << dp[m];
}