题目描述
回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 ^_*）。她发现，把大池子视为01矩阵（0表示对应位置无鱼，1表示对应位置有鱼）有助于决定吃鱼策略。
在代表池子的01矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵“对角线的一端”下口，只一吸，就能把对角线上的那一队鲜鱼吸入口中。
猫猫是个贪婪的家伙，所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下，她一口下去，最多可以吃掉多少条鱼？
输入输出格式
输入格式：
有多组输入数据，每组数据：
第一行有两个整数n和m（n,m≥1），描述池塘规模。接下来的n行，每行有m个数字（非“0”即“1”）。每两个数字之间用空格隔开。
对于30%的数据，有n,m≤100
对于60%的数据，有n,m≤1000
对于100%的数据，有n,m≤2500
输出格式：
只有一个整数——猫猫一口下去可以吃掉的鱼的数量，占一行，行末有回车。
emmmm，刚看到这道题，这不是很显然吗，用f[i][j]表示以(i，j)为正方形的右下角所满足题意的最大正方形的边长，则转移方程为
if(a[i][j] == 1) { int x = f[i - 1][j - 1]; int x1 = i - x, y1 = j - x; if(sum[i][j] - sum[x1 - 1][j] - sum[i][y1 - 1] + sum[x1 - 1][y1 - 1] == x + 1) { f[i][j] = x + 1; } }
再镜面对称过来，嗯，应该A掉了，提交~~~~ ？？？嗯？怎么WA了一组，应该是细节问题，调试~~~~~
两天后......
怎么还没过啊，昧着良心看一下题解吧，wow，竟然有大问题，因为这种做法太过于极端，要不全部保留，要不不保留，所以无法确定该点最大的正方形，应逐一枚举左上那个点的边长，找到能满足的最大值后跳出
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int MAXN = 5e5 + 100; const int MAXM = 3e3 + 10; template < typename T > inline void read(T &x) { x = 0; T ff = 1, ch = getchar(); while(!isdigit(ch)) { if(ch == '-') ff = -1; ch = getchar(); } while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } x *= ff; } template < typename T > inline void write(T x) { if(x < 0) putchar('-'), x = -x; if(x > 9) write(x / 10); putchar(x % 10 + '0'); } int n, m, maxx = -INF, a[MAXM][MAXM], b[MAXM][MAXM], sum[MAXM][MAXM], f[MAXM][MAXM]; int main() { // freopen("1.in", "r", stdin); read(n); read(m); for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { read(a[i][j]); sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j]; } } /* for(int len = 1; len <= min(n, m); ++len) { for(int i = 1; i <= n - len + 1; ++i) { for(int j = 1; j <= m - len + 1; ++j) { int x1 = i + len - 1; int y1 = j + len - 1; if(sum[x1][y1] - sum[i - 1][y1] - sum[x1][j - 1] + sum[i - 1][j - 1] != len * len) continue; } } }*/ for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { if(a[i][j] == 1) { int x = f[i - 1][j - 1]; for(int k = x; k >= 0; --k) { int x1 = i - k, y1 = j - k; if(sum[i][j] - sum[x1 - 1][j] - sum[i][y1 - 1] + sum[x1 - 1][y1 - 1] == k + 1) { f[i][j] = k + 1; break; } } } maxx = max(maxx, f[i][j]); } } // memset(sum, 0, sizeof(sum)); for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { b[i][j] = a[i][m - j + 1]; // sum[i][j] = sum[i][m - j + 1]; sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + b[i][j]; } } for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { if(b[i][j] == 1) { int x = f[i - 1][j - 1]; for(int k = x; k >= 0; --k) { int x1 = i - k, y1 = j - k; if(sum[i][j] - sum[x1 - 1][j] - sum[i][y1 - 1] + sum[x1 - 1][y1 - 1] == k + 1) { f[i][j] = k + 1; break; } } } maxx = max(maxx, f[i][j]); } } write(maxx); putchar(' '); return 0; }