原题链接：Problem - D - Codeforces
题面
题目描述
Alice and Bob are playing a game. Initially, there are $ n $ cakes, with the $ i $ -th cake having a tastiness value of $ a_i $ .
Alice and Bob take turns eating them, with Alice starting first:
- In her turn, Alice chooses and eats any remaining cake whose tastiness is strictly greater than the maximum tastiness of any of the cakes she's eaten before that. Note that on the first turn, she can choose any cake.
- In his turn, Bob chooses any remaining cake and eats it.
The game ends when the current player can't eat a suitable cake. Let $ x $ be the number of cakes that Alice ate. Then, Alice wants to maximize $ x $ , while Bob wants to minimize $ x $ .
Find out how many cakes Alice will eat if both players play optimally.
输入格式
Each test contains multiple test cases. The first line of input contains a single integer $ t $ ( $ 1 \le t \le 500 $ ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 5000 $ ) — the number of cakes.
The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — the tastiness values of the cakes.
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5000 $ .
输出格式
For each test case, output a single integer — the number of cakes Alice will eat if both players play optimally.
样例 #1
样例输入
9 4 1 4 2 3 3 1 1 1 5 1 4 2 3 4 4 3 4 1 4 1 1 8 4 3 2 5 6 8 3 4 7 6 1 1 3 5 3 1 11 6 11 6 8 7 5 3 11 2 3 5 17 2 6 5 3 9 1 6 2 5 6 3 2 3 9 6 1 6样例输出 #1
2 1 3 2 1 3 2 4 4提示
In the first test case, one possible sequence of turns is:
- Alice eats a cake with a tastiness value of $ 1 $ . The remaining cakes are $ [4, 2, 3] $ .
- Bob eats a cake with a tastiness value of $ 2 $ . The remaining cakes are $ [4, 3] $ .
- Alice eats a cake with a tastiness of $ 3 $ . The remaining cakes are $ [4] $ .
- Bob eats a cake with a tastiness value of $ 4 $ . The remaining cakes are $ [] $ .
- Since there are no more cakes left, the game ends.
In the second test case, one possible sequence of turns is:
- Alice eats a cake with a tastiness value of $ 1 $ . The remaining cakes are $ [1, 1] $ .
- Bob eats a cake with a tastiness value of $ 1 $ . The remaining cakes are $ [1] $ .
- Since Alice has already eaten a cake with a tastiness value of $ 1 $ , she cannot make a turn, so the game ends.
解题思路
- 考虑$Alice$的最优方案，她需要保证上一个吃的蛋糕比下一个吃的蛋糕价值小，最优策略只有从蛋糕价值小到大吃这一种。
- 考虑$Bob$的最优方案，如果他要阻止$Alice$吃到第$i$价值的蛋糕，则需要在$Alice$在吃到第$i$蛋糕前将该价值的所有蛋糕都吃完，对答案的贡献为$-1$，否则为$0$。假设共有$cnt$种价值的蛋糕，将它们从小到大排序，它们各有$v_i$个，$Bob$能阻止$Alice$吃到第$i$价值的蛋糕的条件是$Bob$当前吃的蛋糕的个数加上第$i$价值的蛋糕的个数要小于等于$i$ 减去$Alice$已经吃的蛋糕数量。
- 设$dp[i][j]$ 为$Bob$从前 $i$种蛋糕中拿走$j$种蛋糕所需吃的蛋糕数目， 假如$Bob$不拿走第$i$个，$dp[i][j] \leftarrow dp[i - 1][j]$；假设$Bob$拿走第$i$个，$dp[i][j] \leftarrow dp[i - 1][j - 1] + v[i]$，详见代码注释。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 5050;
void Solve() {
ll n; cin >> n;
vector<ll> a(n + 1), c(5050);
for(ll i = 1; i <= n; i ++ ) {
cin >> a[i]; c[a[i]] ++ ;
}
vector<ll> v;
v.push_back(0);
for(ll i = 1; i <= 5000; i ++ ) {
if(c[i] > 0) {
v.push_back(c[i]);
}
}
ll cnt = v.size() - 1;
vector<vector<ll>> dp(cnt + 1, vector<ll>(cnt + 1, inf)); // dp[i][j] Bob 从前 i 种蛋糕中拿走 j 种蛋糕所需的步骤数
dp[1][0] = 0;
for(ll i = 1; i <= cnt; i ++ ) {
dp[i][0] = 0;
for(ll j = 1; j < i; j ++ ) {
dp[i][j] = min(dp[i][j], dp[i - 1][j]); // Bob 不拿走第 i 个，前 i 个蛋糕中拿走 j 个需要的步骤和前 i - 1 个蛋糕中拿走 j 个一样
if(dp[i - 1][j - 1] + v[i] <= i - j) {
dp[i][j] = min(dp[i - 1][j - 1] + v[i], dp[i][j]); // Bob 拿走第 i 个，所需的步骤数即为前 i - 1 个蛋糕拿走 j - 1 个蛋糕的步骤加上拿走第 i 个所需的步骤数
}
}
}
// for(ll i = 1; i <= cnt; i ++ ) {
// for(ll j = 1; j <= cnt; j ++ ) {
// cout << dp[i][j] << " \n"[j == cnt];
// }
// }
ll ans = cnt;
for(ll i = 1; i < cnt; i ++ ) {
if(dp[cnt][i] < inf) ans = min(ans, cnt - i);
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll t; cin >> t;
while(t -- ) {
Solve();
}
return 0;
}