鲜花
校内模拟赛T3，赛时想到了正解的 ，所以就得了 分……
赛后 T 了若干发之后终于过了。
本文提供一种非回退背包的解法。
在下文中，记 。
Solution 1
假设我们修改 ，设用其他数拼出的方案数为 ，那么当 足够大时，有 。所以问题就转化到了求 与 。
考虑枚举 ，并对于每个 进行 DP 计算 。求出最大值与最大值位置（即 ）后，需要求 。
设 表示是否能凑出 。很容易发现，当 时， 合法。暴力枚举即可。
时间复杂度 ，完全不能接受。
Solution 2
我们发现，在第一种解法中，对于同一个物品，进行了太多次的背包 DP。我们尝试只进行一次DP，并标记为了凑出当前这个数，有哪些位置必须被选取。若不需要选取第 个数，代表当我们修改 时仍然能凑出这个数。
具体地，设 表示为了凑出 ，是否需要 。转移方程如下。
$
DP 完之后统计 ，剩余步骤与解法一相同。
时间复杂度仍然是 ，但常数好得多，在洛谷上取得了 分的好成绩！（这也是我赛时的做法，个人认为特别符合直觉。）
Solution 3
考虑优化一下求 的过程。前文已推得，当 ， 不合法。设全集（可重集）为 ，此时有可重集 满足 。再正反做一次背包即可。总时间复杂度 ，还是卡。
Solution 4
由于所有状态都是 或 ，所以可以用 bitset 优化。最终复杂度 ，趋近于 ，可以通过。
Code
在代码中，dp[i][0] 代表文中的 ，其余的 dp[i][j] 代表文中的 。
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
| int n, a[105], sum, cnt[105], mx, p;
bitset<105> dp[700005];
bitset<1400005> tmp;
int main() {
read(n);
for(int i = 1; i <= n; ++i)
read(a[i]), sum += a[i];
sort(a + 1, a + 1 + n);
dp[0] = 1, dp[1][0] = 0;
for(int i = 1; i <= n; ++i)
dp[1][i] = 1;
for(int i = 2; i <= sum; ++i)
dp[i] = dp[i - 1];
for(int i = 1; i <= n; ++i)
for(int j = sum; j >= a[i]; --j)
if(dp[j - a[i]][0]) {
dp[j] &= dp[j - a[i]];
if(!dp[j][0]) dp[j][i] = 1;
dp[j][0] = 1;
}
for(int i = 1; i <= sum; ++i)
if(dp[i][0])
for(int j = 1; j <= n; ++j)
if(!dp[i][j])
++cnt[j];
mx = p = 0;
for(int i = 1; i <= n; ++i)
if(cnt[i] > mx) mx = cnt[i], p = i;
tmp[7000 * n] = 1;
for(int i = 1; i <= n; ++i)
if(i != p)
tmp = tmp | (tmp << a[i]) | (tmp >> a[i]);
for(int i = 1; i <= sum - a[p] + 1; ++i)
if(!tmp[7000 * n + i])
return printf("%d %d\n", a[p], i), 0;
}
|
这代码截止发题解当天竟然还跑出了洛谷最优解。（不过做这道题的人少。）