P8544 「Wdoi-2」禁断之门对面，是此世还是彼世

· · 题解

*K. P8544 「Wdoi-2」禁断之门对面，是此世还是彼世

很棒的一道题目。

先考虑一层 A_i 产生的贡献。

考虑 A_1，它产生的贡献为对于每个 j\in [1, t]，B_{1, j} 与 B_{2, j} 之间所有下标 k 的 A_{1, k} 之和，令其为 g(1)。因为 A_{1, j} = a_1b_j，将 a_1 提出，得 g(1) = a_1h(1)。全局最小值比较难考虑，我们尝试从局部最小值推出全局最小值。我们发现，如果构造出 B_1, B_2 使得 h(1) 最小，那么令 B_3, B_5, \cdots 取到 B_1，B_4, B_6, \cdots 取到 B_2，因为所有 h(i) = h(1)，所以所有 h(i) 取到理论最小值，因而 f(B) 取到最小值。

上述分析使得我们只需要求出 h(1) 的最小值，将其乘上 \sum a_i 后即为 \min f(B)。

进一步地，同一行元素互不相同，这让我们想到二分图匹配。所以 h(1) 的求解又可以描述成如下问题：给定 c_1\sim c_m，求 a_1\sim a_t 和 b_1\sim b_t，使得 a_i 互不相同且 1\leq a_i\leq m，b_i 同理，且 a_i\neq b_i，最小化 \sum\limits_{i = 1} ^ t c(a_i, b_i)，其中 c(x, y) 表示 \sum\limits_{i = \min(x, y)} ^ {\max(x, y)} c_i 且 c_i > 0。

很显然，我们可以用费用流解决上述问题，其中左部点 x 向右部点 y 连容量 1，费用 c(x, y) 的边，则恰好 t 条边的最小费用即答案。这样做的复杂度太高了，即使用 KM 也至少 n ^ 3。但它并不是完全没有用。它告诉我们，答案关于 \boldsymbol t 的函数 \boldsymbol {f(t)} 下凸，因为 最小费用关于流量下凸。这是本题相当关键的性质。

回到上述问题，我们发现使 |x - y| 相差太大并不优秀。带着这样的感性理解，我们先尝试解决 \boldsymbol{m = t} 的情况。此时每个 a_i 都有一个对应的 b_i。如果建出一张 n 个点的图 G，a_i\to b_i 连一条边，那么 G 由若干个环组成，因为每个点出度和入度均为 1。我们容易得到如下观察：

这说明每个环占用一段连续区间 [l, r]。

这说明每个环 [l, r] 形如 l\to l + 1\to \cdots \to r \to l。

上述两条结论对环的形态做出了相当严格的规范，已经可以暴力 DP \mathcal{O}(m ^ 2) 或类插头 DP \mathcal{O}(m) 求解。但我们还可以更劲爆一点。

观察长度为 4 的环 \{1, 2, 3, 4\}，我们发现 c_2, c_3 贡献三次，c_1, c_4 贡献两次。但若将其拆成两个长度为 2 的环 \{1, 2\} 和 \{3, 4\}，c_1\sim c_4 均只贡献两次，更优。而长度为 2 和 3 的环不能再拆分，因为同一列相邻元素不同。因此，任何长度大于 4 的环均可以拆成若干长度为 2 和 3 的环。实际上可以进一步证明长度为 n(n > 4) 的环至多拆出 n\bmod 2 个长度为 3 的环，但对解题不必要。这样一来，直接暴力转移即可做到 \mathcal{O}(m)，比类插头 DP 方便一些。

接下来考虑 \boldsymbol {t < m} 的情况。我们发现相比于 m = t，图 G 上连通块的形态只会新增 链。同理可以证明链必然形如 l\to l + 1\to \cdots \to r，当然也可以反过来 r\to l，但两种情况贡献相等，无需区分。

结合 t = m，我们容易得出 DP f_{i, j} 表示前 i 个点产生 j 条边，且这 j 条边的端点均不超过 i 的最小代价。转移时枚举环长 2, 3 或链长 [2, i] 转移，可以做到 \mathcal{O}(mt ^ 2)。

类似地，我们将链的转移写成类插头 DP 的形式，设 f_{i, j, 0 / 1}，第三维表示当前位置是否有插头，即继续向下延伸的链，则转移形如：

void trans() {
  memset(f, 0x3f, sizeof(f));
  f[0][0][0] = f[1][0][0] = 0;
  for(int i = 2; i <= m; i++) {
    memcpy(f[i], f[i - 1], sizeof(f[i]));
    for(int j = 1; j <= t; j++) {
      f[i][j][1] = min(f[i - 1][j - 1][1], f[i - 2][j - 1][0]) + b[i - 1] + b[i];
    }
    for(int j = 2; j <= t; j++) {
      ll coef = 2 * (b[i - 1] + b[i]);
      f[i][j][0] = min(f[i][j][0], f[i - 2][j - 2][0] + coef);
    }
    if(i > 2) {
      for(int j = 3; j <= t; j++) {
        ll coef = 2 * (b[i - 2] + b[i]) + 3 * b[i - 1];
        f[i][j][0] = min(f[i][j][0], f[i - 3][j - 3][0] + coef);
      }
    }
    for(int j = 0; j <= t; j++) f[i][j][0] = min(f[i][j][0], f[i][j][1]);
  }
}

这样可以做到小常数 \mathcal{O}(m ^ 2)，结合 m = t 可以获得 35 分的高分！

看起来没有什么优化空间了。但这种限制了选取物品个数，且答案关于物品个数具有凸性的 DP，很难不让人想到 wqs 二分。想到这里，结合 m ^ 2 DP，我们已经完整解决了这道题目。如果你不会 wqs 二分，欢迎通过我的 博客 学习。时间复杂度 \mathcal{O}(m\log v)。分析长为 2, 3 的环的贡献差易知 v\leq 3b_i 即 3\times 10 ^ 9。

实际上 “很难不让人想到 wqs” 这句话是在口嗨，因为我自己就没想到。我分析到 m ^ 2 之后一直在想怎么贪心模拟费用流，结果做不动。点开标签一看凸完全单调性豁然开朗。

吐槽一句：a_i = 1 和原问题等难，n, m, t \leq 5\times 10 ^ 4 估计也和正解差不多，所以 35 和 100 分之间没有其它分数。区分度有点低。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;
inline ll read() {
  ll x = 0, sgn = 0;
  char s = getchar();
  while(!isdigit(s)) sgn |= s == '-', s = getchar();
  while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return sgn ? -x : x;
}
inline void print(int x) {
  if(x < 0) return putchar('-'), print(-x);
  if(x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
bool Mbe;
constexpr int N = 5e5 + 5;
constexpr int mod = 1e9 + 7;
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;
void add(int &x, int y) {x += y, x >= mod && (x -= mod);}
struct dat {
  ll val, num;
  dat operator + (const dat &x) const {return {val + x.val, num + x.num};}
  bool operator < (const dat &x) const {
    return val != x.val ? val < x.val : num < x.num;
  }
} f[N][2];
int n, m, t, coef;
ll b[N];
int calc(ll mid) {
  f[0][0] = f[1][0] = {0, 0};
  f[0][1] = f[1][1] = {inf, 0};
  for(int i = 2; i <= m; i++) {
    f[i][0] = f[i - 1][0];
    dat coef = {b[i - 1] + b[i] - mid, 1};
    f[i][1] = min(f[i - 1][1], f[i - 2][0]) + coef;
    coef = {2 * (b[i - 1] + b[i]) - 2 * mid, 2};
    f[i][0] = min(f[i][0], f[i - 2][0] + coef);
    if(i > 2) {
      coef = {2 * (b[i - 2] + b[i]) + 3 * b[i - 1] - 3 * mid, 3};
      f[i][0] = min(f[i][0], f[i - 3][0] + coef);
    }
    f[i][0] = min(f[i][0], f[i][1]);
  }
  return f[m][0].num;
}
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  cin >> n >> m >> t;
  for(int i = 1; i <= n; i++) add(coef, read());
  for(int i = 1; i <= m; i++) b[i] = read();
  ll l = 1, r = 3e9;
  while(l < r) {
    ll mid = l + r + 2 >> 1;
    if(calc(mid) <= t) l = mid;
    else r = mid - 1;
  }
  calc(l);
  cout << (f[m][0].val + l * t) % mod * coef % mod << endl;
  cerr << TIME << " ms\n";
  return 0;
}