「XX Open Cup. GP of Korea」Container

2020 年 08 月 02 日

给定两个长度 $n$ 的序列 $s,t$ ，序列每一位是 $1$ 或 $2$ 。每次你可以选择一个长度 $\leq 3$ 的区间进行左右翻转，代价为区间数值和加上给定常数 $c$ 。问将 $s$ 变换成 $t$ 的最小代价。

$n \leq 500$ 。

题解

非常巧妙的一个题。

我们转化为格路问题， $1$ 表示向右走， $2$ 表示向上走。则 $s$ 和 $t$ 对应的两条路线，被他们的交点分割为若干段。

相当于我们需要用 $1 \times 1, 1 \times 2, 2 \times 1$ 三种长方形填充到两条路线包围住的区间里。不妨先设初始解为全用 $1 \times 1$ 的网格填充，黑白染色后相当于在得到的二分图跑最小费用最大流。

注意到放一个 $2 \times 1$ 的长方形对应的边权是 $2+c$ ， $1 \times 2$ 的长方形对应的边权是 $1+c$ 。一开始我们可以贪心的填 $2 \times 1$ 的长方形，这样剩下未被覆盖的格子只有 $O(n)$ 个。在这个残量网络上跑增广，容易证明至多增广 $O(n)$ 次。

求方案可能还需要跑个拓扑排序。

时间复杂度 $O(n^3 \log n)$ ，然而听说有牛逼的 $O(n^2)$ DP 做法。

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 509, M = 1 << 21;
int n, c, s, t, l, r, ans, cnt, nod, ind[N * N], q[M], pre[M], dis[M], minA[N], minB[N], id[N][N], num[N][N];
int tot = 2, hed[M], nxt[M], to[M], val[M], cst[M];
bool mrk[N][N], inq[M];
string a, b;
vector<int> G[N * N];
vector<pair<int, int>> seq(1), loc(1);
inline void add(int u, int v, int w) {
  nxt[tot] = hed[u], to[tot] = v, val[tot] = 1, cst[tot] = w, hed[u] = tot++;
  nxt[tot] = hed[v], to[tot] = u, val[tot] = 0, cst[tot] = -w, hed[v] = tot++;
}
void way(string &a, int *min) {
  int x = 1, y = 1;
  for (int i = 1; i <= n; i++)
    if (a[i] == '1') {
      min[x] = y;
      for (int i = y; i < N; i++) mrk[x][i] ^= 1;
      ++x;
    } else {
      ++y;
    }
}
bool spfa() {
  memset(pre + 1, 0, nod << 2);
  memset(dis + 1, -63, nod << 2);
  dis[s] = pre[s] = 0;
  q[l = r = 1] = s, inq[s] = true;
  while (l <= r) {
    int u = q[(l++) % M];
    inq[u] = false;
    for (int i = hed[u]; i; i = nxt[i])
      if (val[i] && dis[to[i]] < dis[u] + cst[i]) {
        pre[to[i]] = i;
        dis[to[i]] = dis[u] + cst[i];
        if (!inq[to[i]]) q[(++r) % M] = to[i], inq[to[i]] = 1;
      }
  }
  return pre[t] && dis[t] > 0;
}
int main() {
#ifdef memset0
  freopen("1.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> c >> a >> b;
  a.insert(a.begin(), '\0');
  b.insert(b.begin(), '\0');
  way(a, minA);
  way(b, minB);
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      if (mrk[i][j]) {
        id[i][j] = ++nod;
        loc.push_back({i, j});
        ans += 3 + c;
      }
  s = ++nod, t = ++nod;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      if (mrk[i][j]) {
        if ((i + j) & 1) {
          add(s, id[i][j], 0);
          for (int d = -1; d <= 1; d += 2) {
            if (mrk[i + d][j]) add(id[i][j], id[i + d][j], 2 + c);
            if (mrk[i][j + d]) add(id[i][j], id[i][j + d], 1 + c);
          }
        } else {
          add(id[i][j], t, 0);
        }
      }
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      if (mrk[i][j] && mrk[i + 1][j]) {
        auto connect = [&](int i, int j) {
          int u = id[i][j];
          for (int i = hed[u]; i; i = nxt[i]) {
            if (to[i] == s) return val[i];
            if (to[i] == t) return val[i ^ 1];
          }
          assert(0);
        };
        auto play = [&](int u, int v, int k) {
          for (int i = hed[u]; i; i = nxt[i])
            if (to[i] == v) {
              ans -= k * cst[i];
              val[i] -= k, val[i ^ 1] += k;
            }
        };
        if (!connect(i, j) && !connect(i + 1, j)) {
          int u = id[i][j], v = id[i + 1][j];
          if (!((i + j) & 1)) swap(u, v);
          play(u, s, -1);
          play(u, v, 1);
          play(v, t, 1);
        }
      }
  while (spfa()) {
    int sum = 0;
    for (int i = pre[t]; i; i = pre[to[i ^ 1]]) {
      sum += cst[i];
      val[i]--, val[i ^ 1]++;
    }
    ans -= sum;
  }
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      if (mrk[i][j] && ((i + j) & 1)) {
        int ii = 0, jj = 0;
        for (int k = hed[id[i][j]]; k; k = nxt[k])
          if (to[k] != s && val[k ^ 1]) {
            ii = loc[to[k]].first;
            jj = loc[to[k]].second;
          }
        if (ii && jj) {
          int k = min(i + j, ii + jj) - 1;
          num[i][j] = num[ii][jj] = ++cnt;
          seq.push_back({k, k + 2});
        }
      }
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      if (mrk[i][j] && !num[i][j]) {
        int k = i + j - 1;
        num[i][j] = ++cnt;
        seq.push_back({k, k + 1});
      }
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      if (mrk[i][j]) {
        if (minA[i] < minB[i]) {
          if (mrk[i + 1][j] && num[i][j] != num[i + 1][j]) {
            G[num[i + 1][j]].push_back(num[i][j]);
            ++ind[num[i][j]];
          }
          if (mrk[i][j - 1] && num[i][j] != num[i][j - 1]) {
            G[num[i][j - 1]].push_back(num[i][j]);
            ++ind[num[i][j]];
          }
        } else {
          if (mrk[i - 1][j] && num[i][j] != num[i - 1][j]) {
            G[num[i - 1][j]].push_back(num[i][j]);
            ++ind[num[i][j]];
          }
          if (mrk[i][j + 1] && num[i][j] != num[i][j + 1]) {
            G[num[i][j + 1]].push_back(num[i][j]);
            ++ind[num[i][j]];
          }
        }
      }
  cout << cnt << endl;
  l = 1, r = 0;
  for (int i = 1; i <= cnt; i++)
    if (!ind[i]) q[++r] = i;
  while (l <= r) {
    int u = q[l++];
    cout << seq[u].first << ' ' << seq[u].second << endl;
    for (int v : G[u]) {
      if (!--ind[v]) q[++r] = v;
    }
  }
}

TABLE OF CONTENTS

题解

代码

题解

代码

评论