CF808E Selling Souvenirs

· · 题解

一个牛逼又好写的做法！

首先，因为 w 很小，我们可以先把物品按照性价比排序，然后贪心的选择，最后在小范围内背包（m \le 300）。

这样的话会 WA on #21，因为会被形如这样的数据卡掉：

4001 12000
1 10000
3 10001
3 10001
3 10001
3 10001
3 10001
3 10001
3 10001
3 10001
3 10001
3 10001
...

这样的话虽然 1 的性价比更高，但是会导致钱浪费了，于是我们可以反悔一下，在价格为 1, 2, 3 中分别选择一个最小的价值去返回，然后继续做背包即可。

为什么只需要反悔一个呢？假设我们在上面反悔了多个，显然 \sum w \ge 6 肯定是不优的，如果在之前反悔了很多，然后在下面选这么多肯定还不如之前的。

对于 \sum w < 6 的情况也可以类似去考虑分讨。

然后就做完了。

#include <bits/stdc++.h>
#define int long long

#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)
using namespace std;
const int N = 100005, M = (N << 1), inf = 1e16, mod = 1e9 + 7;
int n, m, ans, sum, f[10], x[4];
struct node {
    int w, c;
    bool operator < (node x) const { return w * x.c < c * x.w; }
} a[N];
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    F(i, 1, n) cin >> a[i].w >> a[i].c;
    sort(a + 1, a + n + 1);
    int pos = 1;
    memset(x, 0x3f, sizeof x);
    while (m > 6 && pos <= n) {
        m -= a[pos].w, sum += a[pos].c;
        if (x[a[pos].w] > a[pos].c) x[a[pos].w] = a[pos].c; pos++;
    }
    if (pos > n) cout << sum, exit(0);
    memset(f, 0xcf, sizeof f); f[0] = 0; 
    F(i, pos, n) dF(j, m + 3, a[i].w) f[j] = max(f[j], f[j - a[i].w] + a[i].c);
    F(i, 1, m + 3) f[i] = max(f[i], f[i - 1]);
    F(i, 1, 3) if (x[i] < inf) ans = max(ans, sum - x[i] + f[m + i]);
    cout << max(ans, sum + f[m]) << '\n';
    return 0;
}