【动态规划】盖房子(house)--未提交--已提交

问题 D: 盖房子(house)

时间限制: 1 Sec 内存限制: 64 MB
提交: 27 解决: 16
[提交][状态][讨论版] </center>

题目描述

FJ最近得到了面积为n*m的一大块土地，他想在这块土地上建造一所房子，这个房子必须膏形的。但是，这块土地并非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。这些瑕疵十分以至于根本不能在上面盖一砖一瓦。他希望找到一块最大的正方形无瑕疵土地来盖房子。不过，不是什么难题，FJ在10分钟内就轻松解决了这个问题。
现在，您也来试试吧。

输入

第1行为两个整数n，m(1≤n，m≤100)。接下来n行，每行m个数字，用空格隔开。0表萄土地有瑕疵，1表示该块土地完好。

输出

一个整数，最大正方形的边长。

样例输入

样例输出

2

思路：自己对于动态规划还是不是很理解，每次做新题总是找不到状态转移方程。
看了网上的解释，总是感觉不清楚，自己想了想，恍然大悟。
可以建立一个数组s[n][m],存储以这个点为右下角的正方形的最大边长。

a[n][m]   0 1 1 1            s[n][m]对应地是   0 1 1 1    
   　　　  1 1 1 0                             1 1 2 2
　　 　　  0 1 1 0                             0 1 2 2 
　　　　   1 1 0 1                             1 1 0 1
状态方程：s[i][j]=min(s[i-1][j],s[i][j-1],s[i-1][j-1])+1;
优化： 观察s[n][m]每次只用那一行以及上一行，所以只需建立s[2][m]的数组就可以。

未优化：

#include <iostream>
#include <cstdio>

using namespace std;

#define minn(a,b,c) (a>b? b:a)>c ? c:(a>b? b:a)

int main()
{
    int n,m;//行列
    int a[105][105]={0};//存储地面状况
    int ans=0;//始终保存最大的边长
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
            if(a[i][j]!=0){
                a[i][j]=(minn(a[i][j-1],a[i-1][j],a[i-1][j-1]))+1;
                ans=max(ans,a[i][j]);
            }
        }
    }
    printf("%d",ans);
    return 0;
}

View Code


优化代码：（错误！）

#include <iostream>
#include <cstdio>

using namespace std;

#define minn(a,b,c) (a>b? b:a)>c ? c:(a>b? b:a)

int main()
{
    int n,m;//行列
    int a[105][105];//存储地面状况
    int s[2][105];//s[i][j]表示以这个点为右下角的正方形的最大边长
    int ans=0;//始终保存最大的边长
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%d",&a[i][j]);
            if(i==0){
                s[0][j]=a[i][j];
            }
            if(i==1&&j==0||j==0&&i!=0){
                s[1][0]=a[1][0];
            }
            if(i!=0&&j!=0){
                if(a[i][j]==0){
                    s[1][j]=0;
                }else{
                    s[1][j]=minn(s[0][j-1],s[0][j],s[1][j-1])+1;
                    ans=max(ans,s[1][j]);
                }
            }
        }
        if(i!=0){
            for(int k=0;k<m;k++){
                s[0][k]=s[1][k];
            }
        }
    }
    printf("%d",ans);
    return 0;
}