D. World is Mine 题解（动态规划， 思维）

原题链接：

https://codeforces.com/contest/1987/problem/D

思路：

动态规划， 思维。

A， B两人吃蛋糕，A吃的蛋糕要求美味度单调递增，所以决定她吃的蛋糕多少就是吃到的蛋糕美味度的种数。

对于答案，A从美味度最小的开始吃，吃到该美味度的一块即有效，而B需要将这个美味度的所有蛋糕都吃掉才有

效，那么我们重点考虑蛋糕美味度的种类。

此时已经明显是一个动态规划。

二维数组记录到第i个蛋糕当B还可以选j次时B完全吃掉的蛋糕种类数。

B不吃当前蛋糕：dp[i][j+1]=dp[i-1][j];

B能吃下当前蛋糕：
   dp[i][j-mp[a[i]]]=max(dp[i-1][j]+1, dp[i][j-mp[a[i]]]);

有点逆向思维

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int xmmm=2e5+10;
int dp[5010][5010];
vector<int>a;
void in(){
    a.clear();
}
void inn(int cnt){
    for(int i=1;i<cnt;i++){
        for(int j=0;j<=i+1;j++){
            dp[i][j]=0;
        }
    }
}
void solve(){
    in();//将a清0；
    int n;cin>>n;
    map<int, int>mp;//统计a数组里面每个元素出现的次数
    for(int i=1;i<=n;i++){
        int t;cin>>t;
        a.push_back(t);mp[t]++;
    }
    sort(a.begin(), a.end());
    int cnt=unique(a.begin(), a.end())-a.begin();//去重， 以及统计现在a数组里面元素个数
    for(int i=1;i<cnt;i++){
        for(int j=0;j<=i;j++)dp[i][j+1]=dp[i-1][j];
        for(int j=0;j<=i;j++){
            if(j>=mp[a[i]]){
                dp[i][j-mp[a[i]]]=max(dp[i-1][j]+1, dp[i][j-mp[a[i]]]);
            }
        }
    }
    int ans=0;
    for(int i=0;i<=cnt;i++)ans=max(ans, dp[cnt-1][i]);
    cout<<cnt-ans<<'\n';
    inn(cnt);//将dp数组初始化
    return ;
}

signed main()
{
    int T;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

总结：

写出这个dp实属不易，在dp更新的地方也想了很久也改了很久。

写出来好多了， 理解更深刻了写出来会更容易。

其实就是想清楚， A先选，B根据是否有足够多的剩余次数去吃下当前蛋糕来更新。