Codeforces 1845E Boxes and Balls 题解

发表于 分类于

思路

考虑如何对一个局面计算所需的最小操作次数．

通过观察可以发现，在操作次数最小的方案中，若将球视为互异的，移动前后所有小球位置的偏序关系不会改变．这很好理解，若在某个方案中，某两个小球移动后位置的偏序关系改变了，那么我们可以通过交换这两个小球的目的地，使操作次数减小．

若设在操作次数最小的方案中，小球 ii 的初始位置是 sis_i，目的地是 tit_i，那么操作次数显然是 ∑i∣si−ti∣\sum_i |s_i - t_i|．很可惜这个限制似乎没法刻画序列的性质，于是我们转而考虑序列中的每一个位置对操作次数造成的贡献．

贡献有两种，从前往后移动经过 ii 的和从后往前移动经过 ii 的．显然两种贡献不能同时存在，那么先考虑第一种贡献，第二种同理可以计算．

第一种贡献统计的是满足 sj≤i<tjs_j \le i < t_j 的 jj 的数量．那么将空盒子看作 00，装了球的盒子看作 11，设初始局面的对应的序列为 aia_i，结束局面对应的序列为 bib_i，那么 ii 位置的贡献就是 ∑j=1iai−∑j=1ibi\sum\limits_{j = 1}^i a_i - \sum\limits_{j = 1}^i b_i．

令 pi=∑j=1iaip_i = \sum\limits_{j = 1}^i a_i，qi=∑j=1ibiq_i = \sum\limits_{j = 1}^i b_i，获得这个局面所需最小的操作次数就是 ∑i∣pi−qi∣\sum_i |p_i - q_i|．

现在要对局面计数，那么我们设 fi,j,rf_{i, j, r} 表示考虑了前 ii 个位置，满足 qi=j,∑x∣px−qx∣=rq_i = j, \sum_x |p_x - q_x| = r 的方案数．考虑当前位置放不放球，转移如下：

fi,j,r=fi−1,j−1,r−∣pi−j∣+fi−1,j,r−∣pi−j∣f_{i, j, r} = f_{i - 1, j - 1, r - |p_i - j|} + f_{i - 1, j, r - |p_i - j|}

由于我们可以使某个球反复横跳来浪费操作次数，那么答案为：

∑j≡k(mod2)fn,pn,j\sum_{j \equiv k \pmod 2} f_{n, p_n, j}

这样做的时间复杂度是 O(nk2)O(nk^2) 的，难以（并不是无法！）通过本题．

然后 鬼知道怎么 发现，有用的转移的 ∣pi−j∣|p_i - j| 是 O(k)O(\sqrt{k}) 级别的．缩小枚举范围即可做到 O(nk1.5)O(nk^{1.5})．

代码

记得滚数组，不然空间寄了．

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
#include <cmath>
#include <cstdio>
#include <cstring>

inline int rd() {
  int x = 0, f = 1, c = getchar();
  while (((c - '0') | ('9' - c)) < 0)
    f = c != '-', c = getchar();
  while (((c - '0') | ('9' - c)) > 0)
    x = x * 10 + c - '0', c = getchar();
  return f ? x : -x;
}

using i64 = long long;
const i64 P = 1e9 + 7;
const int N = 1.5e3;
const int LIM = 40;

int n, k, a[N + 5];
int s[N + 5];
i64 f[2][N + 5][N + 5];

int main() {
  n = rd(), k = rd();
  for (int i = 1; i <= n; i++) a[i] = rd();
  for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
  f[0][0][0] = 1;
  for (int i = 1; i <= n; i++) {
    memset(f[i & 1], 0, sizeof(f[i & 1]));
    for (int j = std::max(0, s[i] - LIM); j <= std::min(s[n], s[i] + LIM); j++) {
      int cost = std::abs(s[i] - j);
      for (int p = cost; p <= k; p++) {
        if (j) (f[i & 1][j][p] += f[(i - 1) & 1][j - 1][p - cost]) %= P;
        (f[i & 1][j][p] += f[(i - 1) & 1][j][p - cost]) %= P;
      }
    }
  }
  i64 ans = 0;
  for (int i = k; i >= 0; i -= 2) (ans += f[n & 1][s[n]][i]) %= P;
  printf("%lld\n", ans);
  return 0;
}