Vijos P1987 – 游戏 [贪心]

Link

https://vijos.org/p/1987

Problem

小雪与小可可正在玩一种数字游戏。他们准备了n卡片，每一张卡片上都有一个整数。游戏开始后，小雪会先选择一个不小于a且不大于b的整数t，并告诉小可可这个数字t是多少。之后小可可会挑出恰好k张卡片，并将这k张卡片上的数字相加，得到的和数记为m。

小雪希望t和m差的绝对值尽可能大，而小可可却希望t和m差的绝对值尽可能小。在游戏开始前，他们二人都知道n，a，b和k是多少，也知道每一张卡片上的数字是多少。在小雪决定了t的大小后，不能再修改，之后才由小可可挑选纸牌。

小雪希望知道，在二人都尝试最优策略的情况下，t和m差的绝对值最大可以有多大？

Analysis

首先遍历A~B设为x, 然后找出卡片能够凑出的最接近于x的数，求abs的最大值就是答案。

所以我们需要找出N张卡片中选K张能够凑出的所有数。思路是dp

dp[i][j]代表前i张卡片，选j张能够凑出的数，可以用一个bitset向量表示每个数能否凑出。转移的话，dp[i][j] = (dp[i-1][j-1] << c[i]) || dp[i-1][j]，其中c[i]表示第i个数的值， (dp[i-1][j-1] << c[i])表示选择第i张卡，dp[i-1][j]表示不选。为了节省空间，可以使用滚动数组。

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 310, inf = 0x3f3f3f3f;
int N, K, A, B;
int v[maxn];
bitset<76000> dp[maxn];
vector<int> ok;

int main() {
    scanf("%d%d%d%d", &N, &K, &A, &B);
    for(int i = 1; i <= N; ++i)
        scanf("%d", v + i);
    dp[0][0] = 1;
    for(int i = 1; i <= N; ++i) {
        for(int j = K; j >= 1; --j) {
            dp[j] |= dp[j-1] << v[i];
        }
    }
    for(int i = 0; i < 76000; ++i)
        if(dp[K][i])
            ok.push_back(i);
    int ans = -1;
    for(int i = A; i <= B; ++i) {
        auto it = lower_bound(ok.begin(), ok.end(), i);
        int cur = inf;
        if(it != ok.end()) cur = min(cur, abs(i - *it));
        if(it != ok.begin()) cur = min(cur, abs(i - *(--it)));
        ans = max(ans, cur);
    }
    printf("%d\n", ans);
    return 0;
}