题解 P1169 【[ZJOI2007]棋盘制作】
题解

先O(n^2)预处理,变成寻找最大同色正方形、矩形。只用对每个点进行arr[i][j]^=(i^j)&1就行了。

第一问DP比较裸,令f[i][j]表示(0,0)-(i,j)的最大正方形边长

若arr[i][j]=arr[i-1][j]=arr[i][j-1]=arr[i-1][j-1]

则f[i][j]=1+min{f[i-1][j],f[i][j-1],f[i-1][j-1]}

否则f[i][j]=1

边界f[0][j]=f[i][0]=1

答案就是最大f[i][j]的平方

第二问有点麻烦,楼下的二维单调队列特别厉害,然而本蒟蒻并没有听懂。我是先dp预处理,令f1[i][j]是(i,j)向上找连续的相同颜色数量,则f1[i][j]=(arr[i][j]==arr[i-1][j]?f1[i-1][j]+1:1),还是比较显然的,f2是向下找连续的相同颜色数量,计算方法和f1一样。

然后枚举行,对于每行中的一段同色区间,计算它上下延展的最大矩形,这个矩形的高显然就是这段区间中f1最小值+f2最小值-1,然后问题就解决了。

我们只用维护当前枚举到的f1、f2的最小值,在每行末尾或arr[i][j]!=arr[i][j-1]时更新ans即可

因为代码比较长,所以只贴上求第二问的代码


/*
const int N = 2003;
int n, m, ans;
bool arr[N][N];
int f1[N][N], f2[N][N];
*/
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            f1[i][j] = f2[i][j] = 1;

    for(int i = 1; i < n; ++i)
        for(int j = 0; j < m; ++j)
            if(arr[i][j] == arr[i - 1][j])
                f1[i][j] = max(f1[i][j], f1[i - 1][j] + 1);
    for(int i = n - 2; i >= 0; --i)
        for(int j = 0; j < m; ++j)
            if(arr[i][j] == arr[i + 1][j])
                f2[i][j] = max(f2[i][j], f2[i + 1][j] + 1);
    ans = 1;
    for(int i = 0; i < n; ++i)
    {
        int c1 = f1[i][0], c2 = f2[i][0];
        int ibeg = 0;
        for(int j = 0; j < m; ++j)
        {
            ans = max(ans, (j - ibeg + 1) * (c1 + c2 - 1));
            if(j == m - 1)
                break;
            if(arr[i][j] != arr[i][j + 1])
            {
                c1 = f1[i][j + 1];
                c2 = f2[i][j + 1];
                ibeg = j + 1;
            }
            else
            {
                c1 = min(c1, f1[i][j + 1]);
                c2 = min(c2, f2[i][j + 1]);
            }
        }
    }
    printf("%d\n", ans);
评论