首页 > 代码库 > 动态规划练习2

动态规划练习2

题目描述:

      lw背上的狂暴药水的作用范围是可以由lw来调控的,但必须是一个正方形(别问我为什么)。但lw有癖好,所以他对每次狂暴的范围有一定的要求。他认为,只有高矮交错的树林才是狂暴的最好范围。给出一片n*m(n,m<=2000)的0/1森林(0为矮,1为高),请找出一个最大的正方形,使得这里面树木高度是交错的。

输入格式:

      第一行两个数,分别为n和m。接下来n行,为一个n*m的0/1矩阵。

输出格式:

      第一行一个数,为最大正方形的边长。

样例输入:rage.in

4 4

1 1 1 0

1 1 0 1

1 0 1 0

0 1 0 1

样例输出:rage.out

3(已标红)

数据范围:

对于30%的数据,n,m<=100。

对于100%的数据,n,m<=2000。

题解:

法一:

对于每一个坐标(i,j)预处理出up[]和left[]分别表示从这个坐标向上和向左最长的交替序列的长度(交替序列即为01相互交错)。

定义状态f[i][j]表示以(i,j)为右下角的正方形最大是多少。

动规方程:if(f[i][j]==f[i-1][j-1])f[i][j]=min(f[i-1][j-1]+1,up[i][j],left[i][j]);

法二:

首先我们分析一下,对于任意一个一个满足题目要求的正方形,被它完全包涵的小正方形必定也是满足题目要求的。

假设以(i,j)为右下角的正方形边长为s,如果包涵(i-1,j)和(i,j-1)这两个点的话,是不是以这两个点为右下角的边长为s-1正方形一定也是满足条件的。

以上是从结果推原因,然后让我们来考虑从原因推结果。

假设我们已经知道以(i-1,j)和(i,j-1)为右下角的边长为s正方形是满足条件的,并且a[i][j]==a[i-s][j-1],那么我们是不是可以推出以(i,j)为右下角的正方形边长为s+1。

接下来就可以解决这道题了。

定义状态:f[i][j]表示以(i,j)为右下角的正方形最大是多少。

转移方程:if(a[i-1][j]==a[i][j-1]&&a[i-1][j]!=a[i][j]&&a[i][j]==a[i-s][j-s])f[i][j]=s+1;

(s为以(i-1,j)和(i,j-1)为右下角的正方形的边长)

 

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int f[2001][2001],a[2001][2001],n,m,ans=1;
int gi()
{
    int ans=0,f=1;
    char i=getchar();
    while(i<0||i>9){if(i==-)f=-1;i=getchar();cout<<i;}
    while(i>=0&&i<=9){ans=ans*10+i-0;i=getchar();}
    return ans*f;
}
int main()
{
    freopen("rage.in","r",stdin);
    freopen("rage.out","w",stdout);
    int i,j,k;
    n=gi();m=gi();
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            a[i][j]=gi();
            f[i][j]=1;
        }
    for(i=2;i<=n;i++)
    {
        for(j=2;j<=m;j++)
        {
            if(a[i-1][j]==a[i][j-1]&&a[i][j-1]!=a[i][j])
            {
                int mmin=min(f[i-1][j],f[i][j-1]);
                for(k=mmin;k>=1;k--)
                {
                    if(a[i][j]==a[i-k][j-k])
                    {
                        f[i][j]=f[i][j]+1;
                        break;
                    }
                } 
                ans=max(ans,f[i][j]);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

 

动态规划练习2