这篇题解主要是这个蒟蒻没看懂其他题解有感而发~
也顺便补充了一下复杂度证明 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。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
#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++) {
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++) {
cout << (dp[i]==1e9?-1:dp[i]) << endl;
}
}
void init() {
}
signed main() {
#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;
while (T--) {
solve();
}
return 0;
}
|