codeforces 808 E. Selling Souvenirs (dp+二分+思维)

题目链接：http://codeforces.com/contest/808/problem/E

题意：最多有100000个物品最大能放下300000的背包，每个物品都有权值和重量，为能够带的最大权值。

物品重量只有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表示背包放了多少，比较一下下一个应该是放2还是放两个1，由于原序列是排好序的，所以如果

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

包最大权值是多少。之后处理一下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;

}

巴特西

codeforces 808 E. Selling Souvenirs (dp+二分+思维)

最新文章

热门文章