题解 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即可 因为代码比较长，所以只贴上求第二问的代码 ```cpp /* 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); ```