BZOJ3997 [TJOI2015] 组合数学

2018 年 03 月 14 日发布.

Description

一个$n\times m$的网格图，每个格子要求了最少经过次数；每次可以向下/向右走，求至少走多少次可以使每个格子走过的次数不小于它的最小经过次数。$n, m\leqslant1000$

Solution

定理：有向图最小路径覆盖等于最大反链长。“反链”是指一些互不可达的点组成的集合。

那么这个问题中“互不可达”就相当于$x1<x2, y1>y2$这样，也就是左上到右下的一条路径。

dp即可。

Code

#include <algorithm>
#include <cstdio>
#include <cstring>
const int N = 1050;
int A[N][N], f[N][N];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    memset(f, 0, sizeof f);
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j)
        scanf("%d", &A[i][j]);
    for (int i = 0; i < n; ++i)
      for (int j = m - 1; ~j; --j) {
        f[i][j] = std::max(A[i][j], f[i][j + 1]);
        if (i) {
          f[i][j] = std::max(f[i][j], f[i - 1][j + 1] + A[i][j]);
          f[i][j] = std::max(f[i][j], f[i - 1][j]);
        }
      }
    printf("%d\n", f[n - 1][0]);
  }
  return 0;
}