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