我O(n^5)的搜索过了……

纪念ac……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 56ms

├ 测试数据 10：答案正确... 525ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：581ms

├ 测试数据 03：运行超时...

├ 测试数据 04：运行超时...

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

四个FOR 类似于1199

呃...

四个循环就过了

貌似类似TJU上的那道“尚未继承的遗产”

这个预处理让我想到了usaco某次月赛的twalk。。。只不过这题用不到。。。

嘻嘻,USACO上的老题了.

O(N^2)的算法才是正道.

这道题目数据不大，才1000，用不着DP。我是4重FOR，搜索过了！

怎么你们都是DP 我可是搜过去的

回楼下：

那个预处理嘛

s=左上角1，1 到 右下角i,j 的石头和

那么s=s+s-s+a

{a表示i,j处是否有石子}

那么从a,b 到 c,d 的石头和就是：

s[c,d]-s[a-1,d]-s[c,b-1]+s[a-1,b-1]

大致这样……有可能笔误

很经典的DP

重点在于想得清楚就好

另：某同学说可以搜过..

至于加速——有一种方法可以用O(n^2)预处理在O(1)时间里得到一个任意矩形内的石头和........

怀疑ing 至少我从来DP 没搜索成功过 尽管用到了那个鸟方法

ps.我知道那个预处理的方法...经常用的...

极其弱智的dp。

设b表示以(i,j)为右上角的最大正方形的边长，则有：

b:=min(b,b,b)+1;

这样程序就很简单了。

（p.s：事实上我从做源程序到所有数据完成一共才用了5分钟^_^）

超弱智的简单方法AC，勿喷谢谢。
#include<bits/stdc++.h>
using namespace std;
int _map[1001][1001]={0};
int main()
{
int n,m,i,j,k,maxx,i1,j1;
bool f;
cin>>n>>m;//n是行，m是列
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
cin>>_map[i][j];
maxx=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(_map[i][j])
{
for(k=i;k<=n;k++)
{
f=true;
for(i1=i;i1<=k;i1++)
for(j1=j;j1<=j+k-i;j1++)
if(!_map[i1][j1])
{
f=false;
break;
}
if(f) maxx=max(maxx,k-i+1);
}
}
cout<<maxx<<endl;
return 0;
}