首页 > 代码库 > 动态规划练习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