这题感觉实在太 educational 了。
容易想到设 \(f_{u, d, l, r}\) 表示 \((u, l), (d, r)\) 这个矩形的复杂度。但是状态数就已经 \(O(n^2m^2)\) 了。
发现矩形复杂度 \(\le \left\lceil{\log n + \log m}\right\rceil\)。考虑交换 dp 状态和答案,设 \(f_{i, u, l, r}\) 表示复杂度 \(\le i\) 的矩形,左上角是 \((u, l)\),右上角是 \((u, r)\) 的矩形,右下角 \((d, r)\) 中 \(d\) 最大能是多少。
转移有分割行和分割列两种情况。注意到分割列时最优切点单调,于是可以双指针。复杂度 \(O(n m^2 (\log n + \log m))\)。
code
// Problem: D - Complexity
// Contest: AtCoder - AtCoder Grand Contest 033
// URL: https://atcoder.jp/contests/agc033/tasks/agc033_d
// Memory Limit: 512 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 190;
int n, m, f[2][maxn][maxn][maxn], a[maxn][maxn];
char s[maxn][maxn];
inline int qsum(int xl, int xr, int yl, int yr) {
return a[xl - 1][yl - 1] + a[xr][yr] - a[xl - 1][yr] - a[xr][yl - 1];
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%s", s[i] + 1);
for (int j = 1; j <= m; ++j) {
a[i][j] = a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1] + (s[i][j] == '#');
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int k = j; k <= m; ++k) {
int l = i, r = n, pos = i - 1;
while (l <= r) {
int mid = (l + r) >> 1;
int t = qsum(i, mid, j, k);
if (t == 0 || t == (mid - i + 1) * (k - j + 1)) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
f[0][i][j][k] = pos;
}
}
}
if (f[0][1][1][m] == n) {
puts("0");
return;
}
for (int d = 1, o = 1;; ++d, o ^= 1) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int k = j, x = j; k <= m; ++k) {
f[o][i][j][k] = max(f[o ^ 1][i][j][k], f[o ^ 1][f[o ^ 1][i][j][k] + 1][j][k]);
while (x + 1 < k && min(f[o ^ 1][i][j][x], f[o ^ 1][i][x + 1][k]) <= min(f[o ^ 1][i][j][x + 1], f[o ^ 1][i][x + 2][k])) {
++x;
}
if (j < k) {
f[o][i][j][k] = max(f[o][i][j][k], min(f[o ^ 1][i][j][x], f[o ^ 1][i][x + 1][k]));
}
}
}
}
if (f[o][1][1][m] == n) {
printf("%d\n", d);
return;
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Complexity AtCoder Contest Grand 033complexity atcoder contest grand atcoder contest grand 033 authentic atcoder contest grand negative atcoder contest grand atcoder contest radius grand atcoder contest grand 001 atcoder contest grand 017 atcoder contest grand 022 atcoder contest grand 039 avoidance atcoder contest grand