題目鏈接：http://codeforces.com/contest/808/problem/E

題意：最多有100000個物品最大能放下300000的背包，每個物品都有權(quán)值和重量，為能夠帶的最大權(quán)值。

物品重量只有3中。重量為1,2,3。

?

題解：可以用3分寫，這里先不介紹。主要講一下二分+dp的方法。首先將重量為1，2，3的物品分別存下來，

然后從大到小排序一下。求一下前綴和，先將1，2二分，因為1，2的取法就兩種要么取2，要么取兩個1代替

2這里就需要二分，比較一下b[mid] and a[k-2*mid+1]+a[k-2*mid+2]的大小，b存的是2，a存的是1，

k表示背包放了多少，比較一下下一個應(yīng)該是放2還是放兩個1，由于原序列是排好序的，所以如果

b[mid]>a[k-2*mid+1]+a[k-2*mid+2]就可以往前二分，反正往后。最后用一個dp[i]表示放了i重量的背

包最大權(quán)值是多少。之后處理一下3就行了。

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const int N = 3e5 + 10;int n, m, a[N], b[N], c[N], an, bn, cn; ll sa[N], sb[N], sc[N], dp[N]; bool cmp(ll x , ll y) {return x > y;} int main() {scanf("%d %d", &n, &m);for (int i = 1; i <= n; i ++) {int w, x;scanf("%d %d", &w, &x);if (w == 1) a[++an] = x;if (w == 2) b[++bn] = x;if (w == 3) c[++cn] = x;}sort(a + 1, a + an + 1, cmp);for (int i = 1; i <= m; i ++) sa[i] = sa[i-1] + a[i];sort(b + 1, b + bn + 1, cmp);for (int i = 1; i <= m; i ++) sb[i] = sb[i-1] + b[i];sort(c + 1, c + cn + 1, cmp);for (int i = 1; i <= m; i ++) sc[i] = sc[i-1] + c[i];dp[1] = sa[1];for (int k = 2; k <= m; k ++) {if (sb[1] <= a[k] + a[k-1]) {dp[k] = sa[k]; continue;}int l = 1, r = k / 2 + 1;while (r > l + 1) {int mid = (l + r) >> 1;if (b[mid] > a[k-2*mid+1] + a[k-2*mid+2]) l = mid;else r = mid;}dp[k] = sb[l] + sa[k-2*l];}for (int i = 1; i <= m; i ++) dp[i] = max(dp[i], dp[i-1]);long long ans = 0;for (int i = 0; i <= cn && i * 3 <= m; i ++) ans = max(ans, sc[i] + dp[m-3*i]);printf("%lld\n", ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/TnT2333333/p/6865879.html

總結(jié)

以上是生活随笔為你收集整理的codeforces 808 E. Selling Souvenirs (dp+二分+思维)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。