题解：P12117 [NWRRC2024] Misère

sunkuangzheng · 2025-04-10 17:59:32 · 题解

首先每种颜色的合法性判断是独立的而且与颜色本身无关，考虑只有一种颜色该怎么做。不难发现我们一定会贪心的删去最大的，并且加入一个手牌里没有的最小牌，正确性显然。

颜色比较多的时候，问题在于可能存在一种策略使得从一个颜色里删去牌并加到另一个颜色里，这些决策是很复杂的，很难直接贪心解决，那么考虑 DP。

可能存在从后面拿牌给前面的情况，看似没法直接 DP。但是注意到，删去的牌可以插入任意颜色，即从不同颜色里删去的牌没有区别。考虑利用这个设计 DP：dp_{i,j} 表示考虑了前 i 种颜色，总共删除了 j 张牌时最少需要插入多少牌使得前 i 堆变得合法。最终 j 是合法的当且仅当 dp_{A,j} \le j。转移就是一个普通的背包。

时间复杂度 \mathcal O(n^2)，可以通过本题。

/**
 *    author: sunkuangzheng
 *    created: 19.11.2024 17:57:57
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5000+5;
using namespace std;
int T,n,A,B,x,y,a[N],b[N]; ll dp[N][N]; vector<int> r[N];
void los(){
    cin >> n >> A >> B; vector<int> c;
    for(int i = 1;i <= n;i ++) cin >> a[i] >> b[i],c.push_back(a[i]);
    sort(c.begin(),c.end()),c.erase(unique(c.begin(),c.end()),c.end());
    A = c.size();
    for(int i = 1;i <= A;i ++) r[i].clear();
    for(int i = 1;i <= n;i ++)
        a[i] = lower_bound(c.begin(),c.end(),a[i]) - c.begin() + 1,r[a[i]].push_back(b[i]);
    for(int i = 0;i <= A;i ++) for(int j = 0;j <= n;j ++) dp[i][j] = 1e18;
    dp[0][0] = 0;
    for(int i = 1;i <= A;i ++){
        int m = r[i].size(); vector<int> pre(m);
        sort(r[i].begin(),r[i].end()); pre[0] = r[i][0] - 1;
        for(int j = 1;j < m;j ++) pre[j] = max(pre[j - 1],r[i][j] - (j * 2 + 1));
        for(int j = 0;j <= m;j ++){
            int ct = (j == m ? 0 : (max(0,pre[m - j - 1]) + 1) / 2);
            for(int k = 0;k <= n - j;k ++)
                dp[i][k + j] = min(dp[i][k + j],dp[i - 1][k] + ct);
        }
    }for(int i = 0;i <= n;i ++) if(dp[A][i] <= i) return cout << i << "\n",void();
    cout << "-1\n";
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}