CF321E Ciel and Gondolas 题解

---

题目链接

• https://codeforces.com/problemset/problem/321/E
• https://m1.oi-archive.org:9000/problem/?oj=bzoj&pid=5311

同时总结一些 DP 优化的方法.

解题思路

• 算法 0: 暴力 DP

考虑 DP. 设 $f(i, j)$ 表示在前 $i$ 个人中, 选出 $j$ 个队伍的最小花费. 那么有转移

$$f(i, j) = \min_{j - 1 \le k \le i - 1} \{ f(k, j - 1) + w(k + 1, i) \}$$

其中 $w(L, R)$ 表示选择 $[L, R]$ 作为一个队伍的花费, 可用利用二维前缀和在 $O(1)$ 的时间内计算. 具体地, 记 $s(i, j)$ 表示 $u$ 的二维前缀和, 那么 $w$ 可表示为

$$w(L, R) = \frac{1}{2} \sum_{i = L} ^ R \sum_{j = L} ^ R u_{i, j} = \frac{1}{2} \big( s(R, R) - s(R, L - 1) - s(L - 1, R) + s(L - 1, L - 1) \big)$$

此时直接计算的时间复杂度为 $O(n ^ 2 k)$. 还有许多优化的空间.

• 算法 1: 四边形不等式优化

观察上面的转移, 对于一个固定的 $j$, 其余部分转移是 1D1D 的形式. 同时, 代价函数 $w$ 同 $j$ 无关, 且满足四边形不等式, 即

$$\forall\ l_1 \le l_2 \le r_1 \le r_2,\ w(l_1, r_1) + w(l_2, r_2) \le w(l_1, r_2) + w(l_2, r_1)$$

如果交换 $f$ 两维的顺序 (也就是该部分的 $f(i, j)$ 在其他部分为 $f(j, i)$), 得到

$$f(i, j) = \min_{i \le k \le j} \{ f(i - 1, k - 1) + w(k, j) \}$$

枚举 $i$, 每次计算 $f(i, j)$ 时 $f(i - 1, j)$ 的值都已确定, 利用决策单调性分治解决即可, 该部分的具体证明和实现可参考 OI Wiki.

时间复杂度 $O(nk \log n)$.

• 算法 2: 凸优化

考虑凸优化, 或者称之为 “wqs 二分” / 带权二分.

如果忽略分作 $k$ 组的限制, 设所分组数为 $x$, 对于每个 $x$, 其最小花费是关于 $x$ 的下凸函数. 证明可参考 Itst: 浅谈满足四边形不等式的序列划分问题的答案凸性.

此时二分斜率 $s$, 对于剩下的问题, 设 $f(i)$ 表示前 $i$ 个人中, 任意选择组成队伍的个数时的最小花费. 则有转移

$$f(i) = \min_{1 < j \le i} \{ f(j - 1) + w(j, i) + s \}$$

同时要记录选出队伍组数以在二分时确定改变斜率的范围.

朴素 DP 的时间复杂度为 $O(n ^ 2 \log w)$, 显得有些鸡肋.

但内层的 DP 还是可以优化的. 实际上, 在 $i$ 一定时, 代价函数 $w$ 关于 $j$ 单调递增, 体现在 $f(i)$ 关于 $i$ 的图像上即为下凸包.

此时维护凸包即可. 在枚举 $i$ 的过程中, 在 $i$ 之前的凸包上的点没有意义, 直接删去. 那么利用双端队列维护凸包. 在向凸包中加入一个点时, 需要二分出其加入的位置, 因此要记录凸包中每一条边两端点所在位置.

维护凸包的操作体现在决策中就是 “决策点会向后更新一段连续的区间”.

时间复杂度 $O(n \log n \log w)$, 其中 $w$ 表示斜率最大值和最小值之差.

代码实现

• 算法 0

// CF321E
// DeP
#include <cctype>
#include <cstdio>
#include <cstring>
using namespace std;

namespace IO {
  const int MAXSIZE = 1 << 18 | 1;
  char buf[MAXSIZE], *p1, *p2;

  inline int Gc() {
    return p1 == p2 &&
      (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
  }
  template<typename T> inline void read(T& x) {
    x = 0; int f = 0, ch = Gc();
    while (!isdigit(ch)) f |= ch == '-', ch = Gc();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
    if (f) x = -x;
  }
}
using IO::read;

template<typename T> inline bool ckmin(T& a, const T& b) {
  return (a > b)? a = b, true: false;
}

const int MAXN = 4e3 + 5, MAXK = 8e2 + 5;
const int INF = 0x3f3f3f3f;

int n, K;
int A[MAXN][MAXN];

int f[MAXN][MAXN];

inline int w(int r1, int c1, int r2, int c2) {
  return (A[r2][c2] - A[r2][c1 - 1] - A[r1 - 1][c2] + A[r1 - 1][c1 - 1]) / 2;
}
inline int w(int L, int R) { return w(L, L, R, R); }

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  read(n), read(K);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      read(A[i][j]), A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];

  for (int i = 0; i <= n; ++i)
    memset(f[i], 0x3f, (K + 1) * sizeof (int));
  f[0][0] = 0;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= i; ++j)
      for (int k = j - 1; k <= i - 1; ++k)
        ckmin(f[i][j], f[k][j - 1] + w(k + 1, i));

  printf("%d\n", f[n][K]);
  return 0;
}

• 算法 1

// CF321E
// DeP
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

namespace IO {
  const int MAXSIZE = 1 << 18 | 1;
  char buf[MAXSIZE], *p1, *p2;

  inline int Gc() {
    return p1 == p2 &&
      (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
  }
  template<typename T> inline void read(T& x) {
    x = 0; int f = 0, ch = Gc();
    while (!isdigit(ch)) f |= ch == '-', ch = Gc();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
    if (f) x = -x;
  }
}
using IO::read;

template<typename T> inline bool ckmin(T& a, const T& b) {
  return (a > b)? a = b, true: false;
}

const int MAXN = 4e3 + 5, MAXK = 8e2 + 5;
const int INF = 0x3f3f3f3f;

int n, K;
int A[MAXN][MAXN];

int f[MAXN][MAXN];

inline int w(int r1, int c1, int r2, int c2) {
  return A[r2][c2] - A[r2][c1 - 1] - A[r1 - 1][c2] + A[r1 - 1][c1 - 1];
}
inline int w(int L, int R) { return w(L, L, R, R) / 2; }

void solve(int* h, const int* g, int L, int R, int kl, int kr) {
  int Mid = (L + R) / 2, k = kl;
  h[Mid] = g[k - 1] + w(k, Mid);
  for (int i = kl + 1; i <= min(kr, Mid); ++i)
    if (ckmin(h[Mid], g[i - 1] + w(i, Mid))) k = i;
  if (L < Mid) solve(h, g, L, Mid - 1, kl, k);
  if (R > Mid) solve(h, g, Mid + 1, R, k, kr);
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  read(n), read(K);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      read(A[i][j]), A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];

  for (int i = 0; i <= K; ++i)
    memset(f[i], 0x3f, (n + 1) * sizeof (int));
  f[0][0] = 0;
  for (int i = 1; i <= K; ++i)
    solve(f[i], f[i - 1], 1, n, 1, n);

  printf("%d\n", f[K][n]);
  return 0;
}

• 算法 2

// CF321E
// DeP
#include <cctype>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <algorithm>
using namespace std;

namespace IO {
  const int MAXSIZE = 1 << 18 | 1;
  char buf[MAXSIZE], *p1, *p2;

  inline int Gc() {
    return p1 == p2 &&
      (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
  }
  template<typename T> inline void read(T& x) {
    x = 0; int f = 0, ch = Gc();
    while (!isdigit(ch)) f |= ch == '-', ch = Gc();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
    if (f) x = -x;
  }
}
using IO::read;

template<typename T> inline bool ckmin(T& a, const T& b) {
  return (b < a)? a = b, true: false;
}

const int MAXN = 4e3 + 5, MAXK = 8e2 + 5;
const int INF = 0x3f3f3f3f;

int n, K;
int A[MAXN][MAXN];

struct Item {
  int v, c;
  Item() { v = c = 0; }
  Item(int _v, int _c): v(_v), c(_c) { }
  Item operator + (const Item& rhs) const {
    return Item(v + rhs.v, c + rhs.c);
  }
  bool operator < (const Item& rhs) const {
    return v < rhs.v || (v == rhs.v && c < rhs.c);
  }
  bool operator <= (const Item& rhs) const {
    return !(rhs < *this);
  }
} f[MAXN];

struct Que {
  int p, L, R;
  Que() { p = L = R = 0; }
  Que(int _p, int _L, int _R): p(_p), L(_L), R(_R) { }
} Q[MAXN];

inline Item F(int j, int i) { // 1 <= j < i
  return f[j] + Item((A[i][i] + A[j][j] - 2 * A[i][j]) / 2, 1);
}

int solve(const int& s) {
  int head = 1, tail = 0;
  Q[++tail] = Que(0, 1, n), f[0] = Item(0, 0);
  for (int i = 1; i <= n; ++i) {
    while (head <= tail && Q[head].R < i) ++head;
    int p = Q[head].p;
    Q[head].L = i, f[i] = Item(F(p, i).v + s, f[p].c + 1);
    if (head > tail)
      Q[++tail] = Que(i, 1, n);
    else if (F(i, n) <= F(p, n)) {
      while (head <= tail && F(i, Q[tail].L) <= F(Q[tail].p, Q[tail].L))
        --tail;
      int L = Q[tail].L, R = Q[tail].R; p = -1;
      while (L <= R) {
        int Mid = (L + R) / 2;
        if (F(i, Mid) <= F(Q[tail].p, Mid)) R = Mid - 1;
        else L = Mid + 1, p = Mid;
      }
      Q[tail].R = p;
      if (p + 1 <= n) Q[++tail] = Que(i, p + 1, n);
    }
  }
  return f[n].c;
}

int main() {
#ifndef ONLINE_JUDGE
  assert(freopen("input.in", "r", stdin));
#endif
  read(n), read(K);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      read(A[i][j]), A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];

  int L = 0, R = A[n][n], ans = -1;
  while (L <= R) {
    int Mid = (L + R) / 2;
    if (solve(Mid) <= K)
      ans = f[n].v - K * Mid, R = Mid - 1;
    else L = Mid + 1;
  }
  printf("%d\n", ans);
  return 0;
}

参考资料

• OI Wiki, 四边形不等式优化.
• Itst, 浅谈满足四边形不等式的序列划分问题的答案凸性
• T_Y_P_E, 【Codeforces 321E / BZOJ 5311】【DP凸优化】【单调队列】贞鱼.

---