自动搬运

查看原文

来自洛谷，原作者为

	sunkuangzheng **

搬运于2025-08-24 23:12:51，当前版本为作者最后更新于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();
}