#include<cstdio>
#include<iostream>
using namespace std;
int i,j,n,m,ans;
int s[1001][1001];
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%d",&s[i][j]);
s[i][j]*=min(s[i-1][j-1],min(s[i-1][j],s[i][j-1]))+1;
if(s[i][j]>ans)
ans=s[i][j];
}
}
printf("%d\n",ans);
return 0;
}

我觉得这个题目对于我这种菜鸟来说，比较新颖，通过f数组来存储当前所能存储的最大正方形边长数，对于f[i][j]来说，如果
f[i-1][j]和f[i-1][j-1]还有f[i][j-1]不为0的情况下，便是已经可以构成已知长度的正方形，如果当前对角线这条边满足条件，即满足f[i][j]=min(f[i-1][j],min(f[i-1][j-1],f[i][j-1]))的情况，便可以在前面构成边长的正方形的基础上+1。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[1001][1001],f[1001][1001];
int main()
{
int n,m,ans=0;
cin>>n>>m;
memset(a,0,sizeof(a));
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j])
{
f[i][j]=min(f[i-1][j],min(f[i-1][j-1],f[i][j-1]))+1;
}
if(f[i][j]>ans) ans=f[i][j];
}
}

/*
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<f[i][j]<<" ";
}
cout<<endl;
}
*/
cout<<ans<<endl;
return 0;
}

数据好弱。。。我以为n^2logn过不了的，没想到过了。。。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1000;
int a[maxn][maxn],x,ans,n,m,sum;
int min(int x,int y)
{
if(x<y) return x;
return y;
}
int main()
{
memset(a,0,sizeof(a));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&x);
a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-1]+x;
}
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
for(int len=1;len<=min(m-i,n-j)+1;len++)
{
sum=a[i+len-1][j+len-1]-a[i+len-1][j-1]-a[i-1][j+len-1]+a[i-1][j-1];
if(sum==len*len&&len>ans) ans=len;
}
printf("%d",ans);
return 0;
}

program v1175;
var g:array[0..101,0..101] of boolean;
f:array[0..101,0..101] of longint;
u:array[0..10201,0..101,0..101] of boolean;
i,j,k,n,m,xx,yy,a,b,x,y,r,p:longint;
procedure fang;
begin
case a of
1: begin
xx:=-1;
yy:=0;
end;
2: begin
xx:=0;
yy:=-1;
end;
3: begin
xx:=1;
yy:=0;
end;
4: begin
xx:=0;
yy:=1;
end;
end;
end;
begin
readln(m,n);
readln(p);
fillchar(g,sizeof(g),false);
for i:=1 to p do
begin
readln(y,x);
g[x,y]:=true;
end;
for i:=0 to n+1 do
begin
g:=true;
g:=true;
end;
for i:=0 to m+1 do
begin
g[0,i]:=true;
g[n+1,i]:=true;
end;
readln(k);
for j:=1 to k do
begin
readln(y,x,a,b);
if g[x,y] then continue;
u[1,x,y]:=true;
fang;
for i:=2 to n+m-1 do
begin
r:=0;
while (g[x+xx,y+yy])and(r<4) do
begin
a:=a+b;
if a>4 then a:=a mod 4;
inc(r);
fang;
end;
if r<4
then begin
x:=x+xx;
y:=y+yy;
u:=true;
end
else break;
end;
end;
fillchar(f,sizeof(f),0);
f[1,1]:=1;
for i:=1 to n do
for j:=1 to m do
if ((i<>1)or(j<>1))and(not u)and(not g)
then f:=f+f;
writeln(f[n,m]);
end.

只有一行一列的情况

之前怎么写过dp的题，所以dp一直是自己的软肋
看了很早之前的walala大神的题解才恍然大悟（在此膜拜~~）

1A
因为大多人喊水就在这里贴思路了
不懂的可看蒟蒻题解：
http://www.cnblogs.com/polebug/p/4005689.html

好水啊！！
program vj1;
var a,f:array[0..1001,0..1001] of longint;
ans,i,j,n,m:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a)
else exit(b);
end;

begin
readln(n,m);
for i:=1 to n do
for j:=1 to m do
read(a[i,j]);

for i:=1 to n do
for j:=1 to m do
if a[i,j]=1 then
begin
f[i,j]:=min(min(f[i,j-1],f[i-1,j]),f[i-1,j-1])+1;
if f[i,j]>ans then ans:=f[i,j];
end;
writeln(ans);
end.

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1002,maxm=1002;
int n,m,x;
int map[maxn][maxm]={0},ans=0;
int main(){
scanf("%d %d\n",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d ",&x);
if(x){
map[i][j]=min(map[i-1][j-1],min(map[i-1][j],map[i][j-1]))+1;
ans=max(ans,map[i][j]);
}
}
}
printf("%d\n",ans);
}
30 ms+4180 KiB

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 2776 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2780 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2776 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 2776 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 2780 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 2776 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 2776 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 2776 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 2780 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 2776 KiB, score = 10
Accepted, time = 15 ms, mem = 2780 KiB, score = 100

// 我只会 JavaScript, 但这里没有相关选项 :<

console.log ('Max length: %d', (function (src) {
    var area = src.split('\n');
    var cord = area.shift().split(' ').map(function (e) { return parseInt(e, 10) });
    var maxX = cord[1],
        maxY = cord[0];

    area = area.map (function (e) { return e.split(' ').map(function (e) {return parseInt(e, 10)}) });
    
    var x = 0, y = 0;
    var isCordBroken = function (x, y) {
        return (area[x] && area[x][y]) !== 1;
    };
    var findCordMax = function (len) {
        console.log ('(%d, %d): %d', x, y, len);
        for (var i = 0; i < len; i++)
        {
            if (isCordBroken(x + len, y)
             || isCordBroken(x, y + len))
            {
                return false;
            }
        }

        var newMax = findCordMax (len + 1);
        return newMax === false ? len : newMax;
    };

    var dMax = 0;
    for (; x < maxX; x++)
    {
        for (; y < maxY; y++)
        {
            if (area[x][y] === 1)
                dMax = Math.max ((findCordMax(1) || 0) + 1, dMax);
        }
    }

    return dMax;
})('4 4\n\
1 1 1 1\n\
1 1 1 1\n\
1 1 1 1\n\
1 1 1 1'));

Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步

var fin:text;
i,j,ans,m,n:integer;
r:array[0..1000,0..1000] of integer;
num:array[1..1000,1..1000] of byte;
function min(a,b:integer):integer;
begin
if a>b then min:=b else min:=a;
end;
begin
assign(fin,'house.in');reset(fin);
readln(fin,n,m);
for i:=1 to n do for j:=1 to m do read(fin,num[i,j]);
close(fin);
fillchar(r,sizeof(r),0);
ans:=0;
for i:=1 to n do
for j:=1 to m do
if num[i,j]=1 then begin
r[i,j]:=min(r[i-1,j-1],min(r[i-1,j],r[i,j-1]))+1;
if r[i,j]>ans then ans:=r[i,j];
end;
writeln(ans);
end.

var
r,c:array[0..1001,0..1001] of longint;
n,m,i,j,ans:longint;

Function min(a,b:longint):longint; begin
if a>b then min:=b else min:=a; end;

begin
readln(n,m);
for i:=1 to n do
for j:=1 to m do
read(c[i,j]);
for i:=1 to n do
for j:=1 to m do
if c[i,j]=1 then begin
r[i,j]:=min(r[i-1,j-1],min(r[i-1,j],r[i,j-1]))+1;
if r[i,j]>ans then ans:=r[i,j];
end;
writeln(ans);
end.

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 16224 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 16220 KiB, score = 10

测试数据 #2: WrongAnswer, time = 0 ms, mem = 16220 KiB, score = 0

测试数据 #3: WrongAnswer, time = 0 ms, mem = 16224 KiB, score = 0

测试数据 #4: Accepted, time = 0 ms, mem = 16224 KiB, score = 10

测试数据 #5: WrongAnswer, time = 0 ms, mem = 16216 KiB, score = 0

测试数据 #6: WrongAnswer, time = 0 ms, mem = 16220 KiB, score = 0

测试数据 #7: WrongAnswer, time = 0 ms, mem = 16220 KiB, score = 0

测试数据 #8: WrongAnswer, time = 0 ms, mem = 16216 KiB, score = 0

测试数据 #9: WrongAnswer, time = 0 ms, mem = 16220 KiB, score = 0

WrongAnswer, time = 0 ms, mem = 16224 KiB, score = 30

代码
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <deque>
#include <queue>
#include <cmath>
#include <map>
#include <time.h>

using namespace std;

int n,m;
int dd[1003][1003];
int dp1[1003][1003];
int dp2[1003][1003];
int dp3[1003][1003];

void solve(){
int maxl;
for (int i = 0; i < n; i++)
{
dp1[i][0] = dd[i][0];
for (int j = 1; j < m; j++){
if (dd[i][j]==1)
dp1[i][j] = dp1[i][j-1]+1;
else dp1[i][j] = 0;
}
}
for (int i = 0; i < m; i++)
{
dp2[0][i] = dd[0][i];
for (int j = 1; j < n; j++){
if (dd[j][i]==1)
dp2[j][i] = dp2[j-1][i]+1;
else dp2[j][i] = 0;
}
}
maxl = 0;
for (int i = 0; i < n; i++){
dp3[i][0] = dp1[i][0];
if (dd[i][0])
maxl = 1;
}
for (int i = 0; i < m; i++){
dp3[0][i] = dp2[0][i];
if (dd[0][i])
maxl = 1;
}

for (int i = 1; i < n; i++)
{
for (int j = 1; j < m; j++){
int v = *dp3[j-1];
if (v){
v++;
v = min(dp1[i][j],v);
v = min(dp2[i][j],v);
dp3[i][j] = v;
maxl = max(maxl,v);
}
else dp3[i][j] = dd[i][j];
}
}

printf("%d\n",maxl);

}

int main(){

scanf("%d %d",&n,&m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
scanf("%d",&dd[i][j]);
}

solve();
return 0;
}

Var a,f:array[0..1000,0..1000] of longint;
i,j,n,m,max,q:longint;
Procedure min(a,b,c:longint);
Begin
If (a<=b) and (a<=c) then q:=a;
If (b<=a) and (b<=c) then q:=b;
If (c<=a) and (c<=b) then q:=c;
End;
Begin
max:=0;
Fillchar(f,sizeof(f),0);
fillchar(a,sizeof(a),0);
Readln(n,m);
For i:=1 to n do
For j:=1 to m do
read(a[i,j]);
For i:=1 to n do
For j:=1 to m do
If a[i,j]=1 then
Begin
min(f[i-1,j],f[i,j-1],f[i-1,j-1]);
F[i,j]:=q+1;
End;
For i:=1 to n do
For j:=1 to m do
If max<f[i,j] then max:=f[i,j];
Writeln(max);
Readln;
End.

好吧，承认自己菜鸟无法秒杀……

测试数据 #0: Accepted, time = 78 ms, mem = 8288 KiB, score = 10

测试数据 #1: Accepted, time = 46 ms, mem = 8288 KiB, score = 10

测试数据 #2: Accepted, time = 46 ms, mem = 8288 KiB, score = 10

测试数据 #3: Accepted, time = 31 ms, mem = 8288 KiB, score = 10

测试数据 #4: Accepted, time = 46 ms, mem = 8288 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 8288 KiB, score = 10

测试数据 #6: Accepted, time = 93 ms, mem = 8288 KiB, score = 10

测试数据 #7: Accepted, time = 46 ms, mem = 8288 KiB, score = 10

测试数据 #8: Accepted, time = 78 ms, mem = 8288 KiB, score = 10

测试数据 #9: Accepted, time = 31 ms, mem = 8288 KiB, score = 10

Summary: Accepted, time = 510 ms, mem = 8288 KiB, score = 100

经典题目，以正方形右下角顶点做一遍DP，AC
program P1057;
var
i,j,ans,n,m:longint;
dp:array[0..1001,0..1001]of longint;
map:array[1..1000,1..1000]of longint;
function min(a,b:longint):longint;
begin
if a<b then
min:=a
else min:=b;
end;
function max(a,b:longint):longint;
begin
if a>b then
max:=a
else max:=b;
end;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(map[i,j]);
dp[i,j]:=map[i,j];
end;
readln;
end;
ans:=1;
for i:=1 to n do
begin
for j:=1 to m do
begin
if (dp[i,j]<>0) then
dp[i,j]:=min(min(dp[i,j-1],dp[i-1,j]),dp[i-1,j-1])+1;
ans:=max(ans,dp[i,j]);
end;
end;
writeln(ans);
end.

点击查看程序源码+详细题解

├ 测试数据 01：答案正确... (0ms, 8252KB)

├ 测试数据 02：答案正确... (0ms, 8252KB)

├ 测试数据 03：答案正确... (0ms, 8252KB)

├ 测试数据 04：答案正确... (0ms, 8252KB)

├ 测试数据 05：答案正确... (0ms, 8252KB)

├ 测试数据 06：答案正确... (0ms, 8252KB)

├ 测试数据 07：答案正确... (0ms, 8252KB)

├ 测试数据 08：答案正确... (0ms, 8252KB)

├ 测试数据 09：答案正确... (0ms, 8252KB)

├ 测试数据 10：答案正确... (0ms, 8252KB)

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

Accepted / 100 / 0ms / 8252KB

暴力+优化=AC

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var n,m,i,j,x,y,len,xx,yy,tot,max,il:longint;

map:array[0..1001,0..1001] of longint;

function min(a,b:integer):integer;

begin

if a>b then exit(b)

else exit(a);

end;

function check:boolean;

var uu,ii:longint;

begin

check:=false;

for uu:=x to x+len-1 do

for ii:=y to y+len-1 do

if map[uu,ii]=-10000 then exit(true);

end;

begin

readln(n,m);

for i:=1 to n do

for j:=1 to m do

begin

read(map);

if map=0 then map:=-10000;

end;

for x:=1 to n do

for y:=1 to m do

begin

for len:=1 to min(n-x+1,m-y+1) do

begin

if check then break;

for xx:=x to x+len-1 do

for yy:=y to y+len-1 do

tot:=tot+map[xx,yy];

if tot>max then

begin

max:=tot;

il:=len;

end;

tot:=0;

end;

end;

writeln(il);

end.

我自己都数不清我用了几重循环了。。。

用了最笨的办法。

dp[i][j] = min(dp[j-1]+1,横着够，竖着够)

a了后看题解是最基础的f(i,j)=min(f(i-1,j-1),f(i,j-1),f(i-1,j))+1

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

int n,m;

int dd[1003][1003];

int dp1[1003][1003];//横着的

int dp2[1003][1003];//竖着的

int dp3[1003][1003];//all

void solve(){

int maxl;

for (int i = 0; i < n; i++)

{

dp1[i][0] = dd[i][0];

for (int j = 1; j < m; j++){

if (dd[i][j]==1)

dp1[i][j] = dp1[i][j-1]+1;

else dp1[i][j] = 0;

}

}

for (int i = 0; i < m; i++)

{

dp2[0][i] = dd[0][i];

for (int j = 1; j < n; j++){

if (dd[j][i]==1)

dp2[j][i] = dp2[j-1][i]+1;

else dp2[j][i] = 0;

}

}

maxl = 0;

for (int i = 0; i < n; i++){

dp3[i][0] = dp1[i][0];

if (dd[i][0])

maxl = 1;

}

for (int i = 0; i < m; i++){

dp3[0][i] = dp2[0][i];

if (dd[0][i])

maxl = 1;

}

for (int i = 1; i < n; i++)

{

for (int j = 1; j < m; j++){

int v = dp3[j-1];

if (v){

v++;

v = min(dp1[i][j],v);

v = min(dp2[i][j],v);

dp3[i][j] = v;

maxl = max(maxl,v);

}

else dp3[i][j] = dd[i][j];

}

}

printf("%d\n",maxl);

}

int main(){

scanf("%d %d",&n,&m);

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

{

scanf("%d",&dd[i][j]);

}

solve();

return 0;

}