Burnling's Blog
0%

CF1987D World is Mine

发表于 更新于 分类于 ，

题意简述

Alice 和 Bob 在玩一个游戏。最初有 $n$ 块蛋糕，第 $i$ 块蛋糕的美味值为 $a_i$。

Alice 和 Bob 轮流吃蛋糕，爱丽丝先开始：

  • 在她的回合中，Alice 选择并吃掉任意一个剩余的、其美味值严格大于她之前吃过的所有蛋糕中最大美味值的蛋糕。注意，在第一回合，她可以选择任何蛋糕。
  • 在他的回合中，Bob 选择并吃掉剩余的蛋糕中的任意一个。

游戏在当前玩家不能吃到合适的蛋糕时结束。设 $x$ 为 Alice 吃掉的蛋糕数量。那么，Alice 想要最大化 $x$，而 Bob 则想要最小化 $x$。

如果双方都采取最优策略，找出 Alice 将吃掉多少块蛋糕。

思路分析

换个角度，这其实是 Alice 每次吃掉一种美味值的蛋糕，Bob 每次吃掉一个蛋糕。

因为 Alice 吃的蛋糕的美味值需要严格大于之前吃过的蛋糕的美味值，所以显然地，将蛋糕按美味值排序后合并，Alice 从小往大吃一定不劣。

而 Bob 相当于负责拦截 Alice。他需要花费 $a_i$ 的回合来阻止 Alice 吃第 $i$ 个蛋糕。

那么，如果 Bob 不能成功阻止 Alice 吃第 $i$ 个蛋糕，他就不应该去浪费回合吃几口就走。

换句话说，Bob 要么花费 $a_i$ 的回合去阻止 Alice，要么不去阻止，不会出现花费若干回合后放弃的情况。

也就是说，这其实是个 0-1 背包问题。

令 $m$ 表示 $n$ 个蛋糕有多少种美味值，令 $\text{num}_i$ 表示第 $i$ 种美味值的蛋糕的个数。

令 $\text{dp}[i][j]$ 表示考虑前 $i$ 种蛋糕，花费了 $j$ 个回合 Bob 最多能吃到的蛋糕数。

每个蛋糕的价值为 $1$，代价为 $\text{num}_i+1$。

为什么代价为 $\text{num}_i+1$ 呢？

因为虽然我们现在仅考虑 Bob 能吃多少蛋糕，但是 Alice 也会一个回合吃一个蛋糕。

又由于 Alice 先手，所以 Alice 吃完后 Bob 才能吃。

所以相当于 Alice 吃的一个蛋糕和 Bob 吃的 $\text{num}_i$ 个蛋糕放在一起算。

所以代价为 $\text{num}_i+1$。

剩下的就是经典的 0-1 背包的套路了。

如果不取第 $i$ 种美味度的蛋糕，那么从上一步到这里不消耗回合数。故 $\text{dp}[i][j]=\text{dp}[i-1][j]$

如果取第 $i$ 种美味度的蛋糕，那么这一步消耗了 $\text{num}+1$ 回合，故 $\text{dp}[i][j]$ 从 $\text{dp}[i-1][j-(\text{num}_i+1)]$ 转移来。

注意回合数要通过逆序枚举来降低复杂度。

最后取 $\text{dp}[m][t],t \in [1,\text{num}_i]$ 的最大值即即为 Bob 的蛋糕数。

剩下的就被 Alice 吃了。

（不要 memset 清空 dp 数组。会变得不幸TLE。）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;

const int maxN = 5100;
int A[maxN];

int N;

struct Cake{
    int tastiness;
    int num;
    Cake(){};
    Cake(int tastiness, int num) : tastiness(tastiness), num(num) {};

    friend bool operator < (Cake A,Cake B){
        return A.tastiness < B.tastiness;
    }
}C[maxN];

int pp = 1;
int dp[maxN][maxN];

inline void solve(){
    scanf("%d",&N);
    for(int i = 1;i<=N;i++) scanf("%d",&A[i]);
    A[N+1] = -1;

    int p = 0;

    sort(A+1,A+1+N);

    int cnt = 1;
    pp = 0;

    for(int i = 2;i<=N+1;i++){
        if(A[i] != A[i-1]){
            C[++pp] = Cake(A[i-1],cnt);
            cnt = 1;
        }else{
            cnt ++;
        }
    }

    int n = pp;
    for(int i = 1;i<=n;i++){
        for(int j = i;j>=0;j--){
            dp[i][j] = max(dp[i][j],dp[i-1][j]);
            if(j - C[i].num - 1 >= 0){
                dp[i][j] = max(dp[i-1][j-C[i].num-1] + 1,dp[i][j]);
            }
        }
    }

    int ma = 0;
 
    for(int i = 0;i<=n;i++){
        for(int j = 0;j<=i;j++){
            ma = max(ma,dp[i][j]);
            dp[i][j] = 0;
        }
    }
    cout << n - ma << endl;

}

int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
}