主要思路：二维DP + 二维前缀和
我就讲讲我当时做这道题的想法就好了。如果你只拿了部分分，可以看看修改和优化方法。
一开始我没看清题，一看，，，这不就是求最长的对角线吗（当时我还只以为是左上右下方向的对角线），，，好求啊，，，简单的dp就好啦
当这个点有鱼时（a[i][j] == 1），最大的长度就是其左上的那个点的最大值+1，如果没鱼，就为0。
if(a[i][j] == 1) f[i][j] = f[i - 1][j - 1] + 1; else f[i][j] = 0;
然后去找所有之中的最大值
但是，显然不对。
后来我又看到了是整个正方形里就只有一条对角线上有鱼，突然想到最大正方形的前缀和做法。相似的，我们用前缀和算出这个正方形的和为对角线的值，不就只有对角线了？
WA了很多，下了一组数据看了看，发现左下右上的对角线也可以，我就把刚刚的操作按左右颠倒重新做了一遍。
还是不对。
为什么？因为我们找的是之中的最大值，如果最大值那个被正方形的那个条件约束住了，就不会寻找比他次大却符合条件的那个答案了。
如果听不懂的话可以对比下我在最后统计答案的代码
正确：
go(i, 1, n, 1)
go(j, 1, m, 1){
while (sum1[i][j] - sum1[i - ooo][j] - sum1[i][j - ooo] + sum1[i - ooo][j - ooo] != f[i][j])
f[i][j]--;
maxx = max(maxx, f[i][j]);} 错误
go(i, 1, n, 1)
go(j, 1, m, 1)
if (sum1[i][j] - sum1[i - ooo][j] - sum1[i][j - ooo] + sum1[i - ooo][j - ooo] == f[i][j])
maxx = max(maxx, f[i][j]); 这样代码是对的，不过那个while真的是烦，我们还得在dp完以后再去找合适的正方形，很浪费时间。
所以，我们可以在dp时就加上正方形的约束条件。
go(i, 1, n, 1)
go(j, 1, m, 1)
if (a[i][j] && sum1[i][j] - sum1[i - oo][j] - sum1[i][j - oo] + sum1[i - oo][j - oo] == f[i - 1][j - 1])
f[i][j] = f[i - 1][j - 1] + 1;
else
f[i][j] = 0; 若部分代码看不懂请到文末代码处寻找define，，，
这样就OK了。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define rep(i, x) for (int i = h[x]; i; i = e[i].nxt)
#define mn 2511
#define inf 2147483647
#define ll long long
#define ld long double
#define fi first
#define se second
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
//#define LOCAL
#define mod
#define Debug(...) fprintf(stderr, __VA_ARGS__)
inline int read(){
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
//This is AC head above...
int n, m, a[mn][mn], f[mn][mn], sum1[mn][mn], sum2[mn][mn],g[mn][mn], maxx = -1;
#define ooo f[i][j]
#define ppp g[i][j]
inline void debug(){
go(i, 1, n, 1)
go(j, 1, m, 1)
printf("%d%c", f[i][j], (j == m ? '\n' : ' '));
puts("");
go(i, 1, n, 1)
go(j, 1, m, 1)
printf("%d%c", g[i][j], (j == m ? '\n' : ' '));
}
int main(){
n = read(), m = read();
go(i, 1, n, 1)
go(j, 1, m, 1)
a[i][j] = read();
go(i, 1, n, 1)
go(j, 1, m, 1)
sum1[i][j] = sum1[i - 1][j] + sum1[i][j - 1] - sum1[i - 1][j - 1] + a[i][j];
go(i, 1, n, 1)
go(j, 1, m, 1)
if (a[i][j])
f[i][j] = f[i - 1][j - 1] + 1;
else
f[i][j] = 0;
go(i, 1, n, 1)
go(j, 1, m, 1){
while (sum1[i][j] - sum1[i - ooo][j] - sum1[i][j - ooo] + sum1[i - ooo][j - ooo] != f[i][j])
f[i][j]--;
maxx = max(maxx, f[i][j]);}
//cout << maxx << "\n";
go(i, 1, n, 1)
fo(j, m, 1, 1)
sum2[i][j] = sum2[i - 1][j] + sum2[i][j + 1] - sum2[i - 1][j + 1] + a[i][j];
go(i, 1, n, 1)
fo(j, m, 1, 1)
if (a[i][j])
g[i][j] = g[i - 1][j + 1] + 1;
else
g[i][j] = 0;
go(i, 1, n, 1)
fo(j, m, 1, 1) {
while (sum2[i][j] - sum2[i - ppp][j] - sum2[i][j + ppp] + sum2[i - ppp][j + ppp] != g[i][j])
g[i][j]--;
maxx = max(maxx, g[i][j]);}
//debug();
cout << maxx;
#ifdef LOCAL
Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
return 0;
} 
京公网安备 11010502036488号