单调队列优化多重背包
PopHirasawa
2021-11-05 11:13:57
Categories:
00算法
>
DP
Tags:
DP
补题补到了个树上背包,然后发现孩子不会。这次就打算把一些该学的背包都学一手?大概。
- 我们知道,对于多重背包,有一个二进制拆分优化,可以在O(vlog(∑n[i]))级别的复杂度解决问题
- 然后单调队列优化可以跑到O(nv)
思路
对于当前物品i,枚举选的个数n[i],用于更新dp数组
然后我们能够发现这样一个神必规律:
dp[i]用于维护代价为i的最大价值,且当前考虑选的物品代价为v
则dp[i]只能够从dp[j],当且仅当j mod v == i mod v 且选的个数不超过要求的点转移过来
也就是
dp[j+nv]=max(dp[j+(n−1)v+w,dp[j+(n−2)v+2w,....)
dp[j+nv]=max(dp[j],dp[j+v]−w,dp[j+2v]−2w,...)+nw
当然,因为有个数的限制,他选定的是一定区间里边的最大值,这个就给我们跑单调区间留下了伏笔捏
CODE
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| #include<iostream> #include<stdio.h> #include<cstring> #include<vector> #include<math.h> #include<algorithm> #include <stdio.h> #include <queue> #include<bitset> #include<map> using namespace std; typedef long long ll; typedef unsigned long long ull; ll N, V; ll f[20000 + 5]; ll g[20000 + 5]; ll q[20000 + 5]; int main() { cin >> N >> V; for (int i = 0; i < N; i++) { ll v, w, s; cin >> v >> w >> s; memcpy(g, f, sizeof(f)); for (int j = 0; j < v; j++) { ll l = 0, r = -1; for (int k = j; k <= V; k += v) { while (r >= l && (k - q[l]) > s * v)l++; while (r >= l && (g[q[r]] - (q[r] - j) / v * w) < (g[k] - (k - j) / v * w))r--; q[++r] = k; f[k] = max(g[k], g[q[l]] + (k - q[l]) / v * w); } } } ll ans = 0; for (int i = 0; i <= V; i++)ans = max(f[i], ans); cout << ans; }
|