自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:40:01，当前版本为作者最后更新于2022-09-12 20:33:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

*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$。我们容易得到如下观察：

• 若存在 $a < b < c < d$ 使得 $a, c$ 在同一个环，$b, d$ 在同一个环，则交换 $b, c$ 一定不会使答案变劣。即 环不相交。

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

• 若存在 $a < b < c < d$ 使得 $a \to c \to b \to d$，则交换 $b, c$ 一定更优，即 边不交叉。

这说明每个环 $[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}$，第三维表示当前位置是否有插头，即继续向下延伸的链，则转移形如：

• $f_{i - 1, j - 1, 1} + c_{i - 1} + c_i\to f_{i, j, 1}$ 表示延伸插头。
• $f_{i - 2, j - 1, 0} + c_{i - 1} + c_i \to f_{i, j, 1}$ 表示新开一个插头。
• $f_{i - 2, j - 2, 0} + 2(c_{i - 1} + c_i) \to f_{i, j, 0}$ 表示新增长度为 $2$ 的环 $\{i - 1, i\}$。
• $f_{i - 3, j - 3, 0} + 2(c_{i - 2} + c_i) + 3c_{i - 1} \to f_{i, j, 0}$ 表示新增长度为 $3$ 的环 $\{i - 2, i - 1, i\}$。
• $f_{i - 1, j, 0}\to f_{i, j, 0}$ 表示啥都不干。
• $f_{i, j, 1} \to f_{i, j, 0}$ 表示在位置 $i$ 断掉插头。注意该转移要在 $f_{i, j, 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;
}