E. Selling Souvenirs 不会做

​​http://codeforces.com/contest/808/problem/E​​

不理解为什么dp = {cost, cnt1, cnt2}可以

而dp = {cost, cnt1, cnt2, cnt3}不可以

上面那个不可以的例子是：

但是这个dp是可行的，只是还有一个更新没实现起来。

dp[i] = dp[i - 2] - (花费为1的元素) + (花费为3的元素)

原来可以按1选择的数目分类，分成奇偶，然后贪心。集训队rank1的zk教我的。cf 2200+ Orz

下面评论有详解

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
#include <time.h>
const int maxn = 300000 + 20;
int a[5][maxn];
int num[33];
struct Node {
    LL val;
    int cnt;
} dp[maxn], dp2[maxn];
bool cmp(int x, int y) {
    return x > y;
}
LL sum[maxn];
LL odd[maxn], even[maxn];
LL sum3[maxn];
void work() {
    int n;
    scanf("%d", &n);
    int m;
    scanf("%d", &m);
    int lenOdd = 0, lenEven = 0;
    for (int i = 1; i <= n; ++i) {
        int id, x;
        scanf("%d", &id);
        scanf("%d", &a[id][++num[id]]);
        if (id == 2) {
            odd[++lenOdd] = even[++lenEven] = a[id][num[id]];
        }
    }
    for (int i = 1; i <= 3; ++i) {
        sort(a[i] + 1, a[i] + 1 + num[i], cmp);
    }

    for (int i = 1; i <= num[3]; ++i) {
        sum3[i] = sum3[i - 1] + a[3][i];
    }

    for (int i = 1; i <= num[1]; i += 2) {
        if (i + 1 > num[1]) break;
        even[++lenEven] = a[1][i] + a[1][i + 1];
    }
    sort(even + 1, even + 1 + lenEven, cmp);
    for (int i = 1; i <= lenEven; ++i) {
        even[i] = even[i] + even[i - 1];
    }
    LL ans = 0;
    for (int i = 0; i <= m; ++i) { //even个，暴力枚举用在另外两个的总量是多少
        LL res = even[min(lenEven, i / 2)];
        LL res2 = sum3[min((m - i) / 3, num[3])];
        ans = max(res + res2, ans);
    }

    for (int i = 2; i <= num[1]; i += 2) {
        if (i + 1 > num[1]) break;
        odd[++lenOdd] = a[1][i] + a[1][i + 1];
    }
    sort(odd + 1, odd + 1 + lenOdd, cmp);
    for (int i = 1; i <= lenOdd; ++i) {
        odd[i] = odd[i - 1] + odd[i];
    }
    LL ans2 = 0;
    for (int i = 0; i <= m - 1; ++i) {
        LL res = odd[min(lenOdd, i / 2)];
        LL res2 = sum3[min(num[3], (m - i - 1) / 3)];
        ans2 = max(ans2, res + res2);
    }
    cout << max(ans, ans2 + a[1][1]) << endl;
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    work();
    return 0;
}

View Code