这题的关键是矩阵中的每个元素都是 >=0 的， 然后就可以找到递增性质. 也就是如果N*N个方块满足小于或等于limit 那么(N-1)*(N-1)个方块也是满足的.

 

Problem 2056 最大正方形

Accept: 75    Submit: 287

Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

现在有一个n*m的矩阵A，在A中找一个H*H的正方形，使得其面积最大且该正方形元素的和不大于 limit。

Input

第一行一个整数T，表示有T组数据。

每组数据 第一行三个非负整数 n m limit

接着 n 行，每行 m 个整数。

 

0 < n <= 1000, 0 < m <= 1000, 0 <= limit <=100000000 0 <= A[i] <= 1000

Output

对于每组数据，输出H*H。

Sample Input

2 2 2 2 1 1 1 1 2 2 4 1 1 1 1

Sample Output

1 4

Source

FOJ有奖月赛-2011年11月

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define N 1010int dp[N][N]; //存前i，j矩阵的和int n,m,lm;int fuc(int s){    if(s==0) return 1;    for(int i=s;i<=n;i++)        for(int j=s;j<=m;j++)        {            int sum=dp[i][j]-dp[i-s][j]-dp[i][j-s]+dp[i-s][j-s];            if(sum<=lm)             {                    return 1;            }        }    return 0;}int main(){    int t;    scanf("%d",&t);    while(t--)    {        scanf("%d%d%d",&n,&m,&lm);        memset(dp,0,sizeof(dp));        for(int i=1;i<=n;i++)        {            int sum=0;            for(int j=1;j<=m;j++)            {                int tmp;                scanf("%d",&tmp);                sum+=tmp;                dp[i][j]=dp[i-1][j]+sum;            }        }        int  b=0,d=min(n,m);        while(b