LOJ #3503. 「联合省选 2021 A | B」滚榜

显然每一轮的 \(b_i\) 越小越好, 于是问题可以转化为每一次拓展最小的 \(b_i\), 且 \(\sum b_i\le m\).

可以想到一个状压 \(\text{DP}\) : 设 \(f(S,\,i,\,j,\,k)\) 表示序列中已有集合 \(S\) , 其中最后一个为 \(i\) , 且 \(b_i=j,\ \sum\limits_{i\in S}b_i=k\) . 直接暴力转移, 时间复杂度为 \(\mathrm O(2^n\cdot n^2\cdot m^2)\) . 显然过不去.

注意到这个 \(m^2\) 特别烦, 我们需要的是序列 \(p_i\) 的个数, 而不是划分数组 \(b_i\) 的个数. 状态记录最后一个位置 \(i\) 与位置 \(i\) 所对应的 \(b_i\) 感觉是多余的, 但上述 \(\text{DP}\) 中的任何一维似乎都不能消去. 于是考虑换个思路, 寻找性质.

注意到 \(b_i\) 必须是单调递增的. 而且在上面的 \(\text{DP}\) 过程中, 我们要求的是 \(\sum{b_i}\le m\) , 而不是具体每一个 \(b_i\) 的值. 于是可以构造出 \(b\) 数组的差分数组 \(c\) , 那么就有 \(m\ge \sum\limits_{1\le i\le n}b_i=\sum\limits_{1\le i\le n}c_{p_i}(n-i+1)\) . 由于 \(n-i+1\) 可以在 \(\text{DP}\) 过程中顺带求出, 现在只需考虑给定 \(i,j\) 如何求出 \(c_{j,i}=b_j-b_i\) .

由 \(a_j+b_j+[j<i]>a_i+b_i\) 知, \(c_{j,\,i}=b_j-b_i\ge a_i-a_j+1-[j<i]=a_i-a_j+[j>i]\)

注意到 \(c_{j,\,i}\ge 0\) , 因此上式还要和 \(0\) 取 \(\max\)

因此做法就是预处理出 \(c_{j,\,i}\) , 然后设 \(f(S,\,i,\,k)\) 表示序列中已有集合 \(S\) , 其中最后一个为 \(i\) , 且 \(\sum\limits_{i\in S}b_i=k\) . 转移是

最后的答案就是 \(\sum f(\{1,2,\ldots n\},\,i,\,k)\) , 其中 \(i,k\) 任意.

总时间复杂度为 \(\mathrm O(2^n\cdot n^2\cdot m)\) , 可以通过.

#include <bits/stdc++.h>
using namespace std;
static constexpr int Maxn = 13, Maxm = 505;
int n, m;
int a[Maxn];
int d[Maxn][Maxn];
int64_t f[1 << Maxn][Maxn][Maxm];
int main(void) {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j)
    d[j][i] = max(0, a[i] - a[j] + (i < j));
  memset(f, 0, sizeof(f));
  for (int i = 0; i < n; ++i)
    f[(1 << i)][i][n * *max_element(d[i], d[i] + n)] = 1;
  for (int s = 1; s < (1 << n); ++s)
    for (int i = 0; i < n; ++i) if ((s >> i & 1))
      for (int k = 0; k <= m; ++k)
        if (f[s][i][k]) {
          int l = __builtin_popcount(s);
          for (int j = 0; j < n; ++j) if (!(s >> j & 1)) {
            int c = (n - l) * d[j][i];
            if (k + c <= m) f[s | (1 << j)][j][k + c] += f[s][i][k];
          }
        }
  int64_t ans = 0;
  for (int i = 0; i < n; ++i)
    for (int k = 0; k <= m; ++k)
      ans += f[(1 << n) - 1][i][k];
  printf("%lld\n", ans);
  exit(EXIT_SUCCESS);
} // main