题解 [AGC033D] Complexity

Leasier · 2022-11-09 17:51:15 · 题解

首先，我们不难想到一个暴力 dp：设 dp_{i, j, k, l} 表示左上角为 (i, k)、右下角为 (j, l) 的矩形的复杂度。转移时直接分两种情况枚举分界点即可。时间复杂度为 O(n^5)，显然不能通过。

但此时我们注意到一个问题：答案是很小的，因为我们可以通过每次在两个维度之一上二分做到 \leq \lceil \log_2 n \rceil + \lceil \log_2 m \rceil 的复杂度。

考虑交换状态和答案，改设 dp_{i, j, k, l} 表示复杂度 \leq i 时，左上角为 (j, k)，右上角为 (j, l) 时右下角 x 坐标的最大值。

初值：dp_{0, i, j, k} = \max l，其中左上角为 (i, j)、右下角为 (l, k) 的矩形中所有元素颜色相同。

转移分为如下三种情况。

• 矩形 (j, k, l) 复杂度 \leq i - 1 时，其复杂度也一定 \leq i，则 dp_{i, j, k, l} \leftarrow \max(dp_{i, j, k, l}, dp_{i - 1, j, k, l})。
• 横着切一刀，此时我们贪心地一定会尽量从满足复杂度 \leq i - 1 且最大的位置切开，则 dp_{i, j, k, l} \leftarrow \max(dp_{i, j, k, l}, dp_{i - 1, dp_{i - 1, j, k, l} + 1, k, l})。
• 竖着切一刀，此时我们需要枚举切点，则 dp_{i, j, k, l} \leftarrow \max(dp_{i, j, k, l}, \displaystyle\max_{x = k}^{l - 1} \min(dp_{i - 1, j, k, x}, dp_{i - 1, j, x + 1, l}))。

答案：\min i，其中 dp_{i, 1, 1, m} = n。

直接做的时间复杂度是 O(nm^3 (\log n + \log m))，看上去很不能过，但事实上它在 AT 上冲过了，最大用时不超过 3s（

但是这道题在今天的模拟赛中的数据范围达到了 250，这个做法过不去了……

要是我们能不枚举竖着的切点就好了！打印出切点会发现：i, j, k 不变时，l 增大，切点 x 单调不降。

知道这一条性质后对切点双指针即可。时间复杂度为 O(nm^2 (\log n + \log m))。

证明：首先我们知道 i, j, k 不变时，l 增大，dp_{i, j, k, l} 单调不降。

我们将 dp_{i, j, k, x}, dp_{i, j, x + 1, l} 视为两个分别不降和不增的函数，当 l 增大，第一个函数图像不变，但第二个函数图像下移，感性理解可知取 \min 后最高点不会左移。

代码：

#include <stdio.h>
#include <math.h>

int sum[187][187], dp[7][187][187][187];
char s[187][187];

inline int get_sum(int l1, int r1, int l2, int r2){
    return sum[r1][r2] - sum[r1][l2 - 1] - sum[l1 - 1][r2] + sum[l1 - 1][l2 - 1];
}

inline int max(int a, int b){
    return a > b ? a : b;
}

inline int min(int a, int b){
    return a < b ? a : b;
}

int main(){
    int n, m, k;
    scanf("%d %d", &n, &m);
    k = ceil(log2(n)) + ceil(log2(m));
    for (int i = 1; i <= n; i++){
        scanf("%s", &s[i][1]);
        for (int j = 1; j <= m; j++){
            sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + (s[i][j] == '.' ? 1 : 0);
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            int pos = n;
            for (int x = j; x <= m; x++){
                while (pos >= i){
                    int y = get_sum(i, pos, j, x);
                    if (y == 0 || y == (pos - i + 1) * (x - j + 1)) break;
                    pos--;
                }
                if (pos < i) break;
                dp[0][i][j][x] = pos;
            }
        }
    }
    if (dp[0][1][1][m] == n){
        printf("0");
        return 0;
    }
    for (int i = 1; i <= k; i++){
        int cur = i & 1, pre = cur ^ 1;
        for (int j = 1; j <= n; j++){
            for (int x = 1; x <= m; x++){
                int pos = x;
                for (int y = x; y <= m; y++){
                    while (pos + 1 < y && min(dp[pre][j][x][pos], dp[pre][j][pos + 1][y]) <= min(dp[pre][j][x][pos + 1], dp[pre][j][pos + 2][y])) pos++;
                    dp[cur][j][x][y] = max(dp[pre][j][x][y], max(dp[pre][dp[pre][j][x][y] + 1][x][y], min(dp[pre][j][x][pos], dp[pre][j][pos + 1][y])));
                }
            }
        }
        if (dp[cur][1][1][m] == n){
            printf("%d", i);
            return 0;
        }
    }
    return 0;
}