这篇题解主要是这个蒟蒻没看懂其他题解有感而发~

也顺便补充了一下复杂度证明qwq。

前置芝士：

• 背包
• 三角形不等式

---

题目大意

题目给出 $N$ 组 ${A_i,B_i}$，求选择 $k$ 个组选择 $B_i$ 剩下组选择 $A_i$ 可以得到的最大权值，$k = 0,1,2,…,M$，$M$ 是定值

思路

问题转化

假设我们现在全部取 $A_i$，则权值就是

$$\sum_{i=1}^{n}{A_i}$$

设这个值为 $S$，再定义一个 $D$ 数组，表示每张卡牌的 变化量：

$$ D_i = B_i - A_i $$

所以我们知道：

• 如果选 $A_i$ ： 当前贡献 $ = A_i$
• 如果选 $B_i$ : 当前贡献 $ = A_i + D_i = B_i $

初始时总和 $ S = \sum A_i$。

选了若干个 $B_i$ 后：

$$ now = S + \sum_{i \in T}{D_i} $$

对于每个 $k$ 我们要找：

$$ S + \sum_{i \in T}{D_i} = k $$

初步思路

实际上上边那段看不懂也没关系，总结一句，上面就是对每个 $i$ 都选择选 $A_i$ 还是 $B_i$ （题目中的翻或者不翻），突然发现，这不就是一个01背包问题吗？（哇我真是甜菜）

状态定义如下：

$$ dp[i]：总和为 k 的时候至少要翻多少次 $$

（这里默认把原来的 $N$ 滚动掉了）

转移很简单：

$$ dp[i] = max(dp[i], dp[i-D_i]+1) $$

但是考虑到 $D_i$ 可能是负数，所以判断一下

$$ dp[i] = max(dp[i], dp[i-D_i]+1) [0 \leq D_i] $$

$$ dp[i] = max(dp[i], dp[i-D_i]+1) [D_i < 0] $$

乍一看好像没啥区别？实际上，这关乎到背包的第二层遍历。实际上第二个式子应该是 $dp[i+abs(D_i)]+1$，这里化简了，并且，遍历的时候负数是要从左往右的。

只不过算一算复杂度，发现卡片 $O(N)$，总和 $O(M)$，乘起来就是 $O(NM)$，所以会超时。气煞我也！！！

优化

这时候我们分类讨论：

• $D_i \leq \sqrt{M}$ 这时候差值范围是 $[-\sqrt{M},\sqrt{M}]$，总共有 $2*sqrt{M}+1$ 种情况。

• $\sqrt{M} < D_i$ 我们知道最多有 $3*\sqrt{M}+1$ 种 $D_i$，证明如下：

首先根据三角形不等式，我们知道：

$$ |B_i - A_i| \leq A_i + B_i $$

$$ 又因为 \sum_{i=1}^{N}{(A_i+B_i)} = M $$

$$ 所以 \sum_{i=1}^{N}{| B_i-A_i |} \leq M $$

$$ 又有 \sqrt{M} < D_i $$

$$ 就可以得到 | B_i-A_i | 的种类数 < \frac{M}{\sqrt{M}} = \sqrt{M} $$

所以最多有 $ 2*\sqrt{M} + 1 + \sqrt{M} $ 种 $D_i$ 的情况

所以，我们可以把 $M$ 个 $D_i$ 转换成最多 $3*\sqrt{M}+1$ 个数，然后用多重背包压缩去做，这时候复杂度就是 $O(Nsqrt{M} + Nlog{M}) = O(N*sqrt{M})$，于是就可以过掉这道题啦~

代码

放一下我丑陋的代码qwq。

/**
 * Problem: AT_abc269_g [ABC269G] Reversible Cards 2
 * File: AT_abc269_g [ABC269G] Reversible Cards 2.cpp
 * Create Date: 2025/10/17 21:32
 * Last Change Date: 2025/10/17 21:32
 * Editor: code-server
 * Powered by 1000ttank
 */
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define int __int128
#define endl '\n'

void solve() {
    int n,k; cin >> n >> k;
    vector<int> a(n+1,0),b(n+1,0);
    map<int,int> tm;
    int init=0;
    for (int i=1;i<=n;i++) {
        cin >> a[i] >> b[i];
        init+=a[i];
        tm[b[i]-a[i]]++;
    }
    vector<int> w(1),v(1);
    for (auto i:tm) { // 预处理多重背包
        int t=i.second,tw=i.first;
        int base=1;
        while (t>=base) {
            t-=base;
            w.push_back(base);
            v.push_back(base*tw);
            base*=2;
        }
        if (t) {
            w.push_back(t);
            v.push_back(t*tw);
        }
    }
    int m=w.size()-1;
    vector<int> dp(k+1,1e9); dp[init]=0;   
    for (int i=1;i<=m;i++) { // 多重背包，实际上就是个 01背包，只不过压缩了物品
        if (v[i]>0) {
            for (int j=k;j>=v[i];j--) {
                dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
            }
        } else {
            for (int j=0;j<=k+v[i];j++) {
                dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
            }
        }
    }
    for (int i=0;i<=k;i++) { // 注意判 inf 哦~
        cout << (dp[i]==1e9?-1:dp[i]) << endl;
    }
}
void init() {
    
}
signed main() {
    // #Define CONTEST_MODEL
    #ifdef CONTEST_MODEL
    #ifndef LOCAL 
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
    #endif
    #endif

    ios::sync_with_stdio(false); cin.tie(nullptr);
    init();
    int T=1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}