本文主要是介绍动态规划——悬线法 （P1169 棋盘制作 p4147 玉蟾宫 p2701 巨大的牛棚 p1387 最大正方形），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
学习于luogu p1169 第一篇题解
悬线法
用途:
解决给定矩阵中满足各种条件的最大子矩阵
做法:
用一条线(横竖貌似都行)左右移动直到不满足约束条件或者到达边界
定义数组:
le[i][j]: 代表从(i,j)能到达的最左位置
ri[i][j]: 代表从(i,j)能到达的最右位置
up[i][j]: 代表从(i,j)向上扩展最长长度.
预处理：
for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){cin>>mp[i][j];up[i][j]=1; //向上的宽度为1ri[i][j]=le[i][j]=j; //到达的最左最右都是本身}
}递推公式：
先处理le和ri数组：(以p1169举例，条件为相邻的不相同)
for(int i=1;i<=n;++i){for(int j=2;j<=m;++j){//处理左边界le if(mp[i][j]!=mp[i][j-1]) le[i][j]=le[i][j-1];//如果满足条件，那le[i][j]就可以往左挪一挪 等于le[i][j-1]}for(int j=m-1;j>=1;--j){//处理右边界riif(mp[i][j]!=mp[i][j+1]) ri[i][j]=ri[i][j+1];}
}处理up数组的同时，再一次处理le和ri数组
for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){if(i>1 && mp[i][j]!=mp[i-1][j]){ //向上满足条件le[i][j]=max(le[i][j],le[i-1][j]); //le代表从该坐标点 厚度/宽度 为up[i][j]的最大左边界ri[i][j]=min(ri[i][j],ri[i-1][j]); //同理up[i][j]=up[i-1][j]+1; //向上的宽度在up[i-1][j]的基础上+1}int a=ri[i][j]-le[i][j]+1;int b=min(a,up[i][j]);res1=max(res1,b*b);res2=max(res2,a*up[i][j]);}
}例题：
P1169 [ZJOI2007]棋盘制作
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int maxn=2005;
int n,m,mp[maxn][maxn];
int ri[maxn][maxn],le[maxn][maxn],up[maxn][maxn];
int main(){std::ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){cin>>mp[i][j];up[i][j]=1;ri[i][j]=le[i][j]=j;}}for(int i=1;i<=n;++i){for(int j=2;j<=m;++j){//处理左边界le if(mp[i][j]!=mp[i][j-1]) le[i][j]=le[i][j-1];}for(int j=m-1;j>=1;--j){//处理右边界riif(mp[i][j]!=mp[i][j+1]) ri[i][j]=ri[i][j+1];}}int res1=-inf,res2=-inf;for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){if(i>1 && mp[i][j]!=mp[i-1][j]){le[i][j]=max(le[i][j],le[i-1][j]);ri[i][j]=min(ri[i][j],ri[i-1][j]);up[i][j]=up[i-1][j]+1;}int a=ri[i][j]-le[i][j]+1;int b=min(a,up[i][j]);res1=max(res1,b*b);res2=max(res2,a*up[i][j]);}}cout<<res1<<endl<<res2<<endl;return 0;
}P4147 玉蟾宫
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int maxn=1e3+5;
int n,m;
int le[maxn][maxn],ri[maxn][maxn],up[maxn][maxn],ans=-inf;
char mp[maxn][maxn];
int main(){std::ios::sync_with_stdio(0);cin>>n>>m;char tt;for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){cin>>mp[i][j];if(mp[i][j]=='F') le[i][j]=ri[i][j]=j,up[i][j]=1;}}for(int i=1;i<=n;++i){for(int j=2;j<=m;++j){if(mp[i][j-1]=='F' && mp[i][j]=='F'){le[i][j]=le[i][j-1];}}for(int j=m-1;j>=1;--j){if(mp[i][j+1]=='F' && mp[i][j]=='F'){ri[i][j]=ri[i][j+1];}}}for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){if(i>1 && mp[i-1][j]=='F' && mp[i][j]=='F'){le[i][j]=max(le[i][j],le[i-1][j]);ri[i][j]=min(ri[i][j],ri[i-1][j]);up[i][j]=up[i-1][j]+1;}if(mp[i][j]=='F'){int a=ri[i][j]-le[i][j]+1;ans=max(ans,a*up[i][j]);}}}cout<<ans*3<<endl;return 0;
}P2701 [USACO5.3]巨大的牛棚Big Barn
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int maxn=1e3+5;
int n,T,ans=-inf;
int mp[maxn][maxn],ri[maxn][maxn],le[maxn][maxn],up[maxn][maxn];
int main(){std::ios::sync_with_stdio(0);cin>>n>>T;int x,y;for(int i=1;i<=T;++i){cin>>x>>y;mp[x][y]=1;}for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){if(!mp[i][j]) le[i][j]=ri[i][j]=j,up[i][j]=1;}}for(int i=1;i<=n;++i){for(int j=2;j<=n;++j){if(!mp[i][j] && !mp[i][j-1]) le[i][j]=le[i][j-1];}for(int j=n-1;j>=1;--j){if(!mp[i][j] && !mp[i][j+1]) ri[i][j]=ri[i][j+1];}}for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){if(i>1 && !mp[i][j] && !mp[i-1][j]){le[i][j]=max(le[i][j],le[i-1][j]);ri[i][j]=min(ri[i][j],ri[i-1][j]);up[i][j]=up[i-1][j]+1;}if(!mp[i][j]){int a=ri[i][j]-le[i][j]+1;a=min(a,up[i][j]);ans=max(ans,a);}}}cout<<ans<<endl;return 0;
}P1387 最大正方形
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int maxn=1e3+5;
int n,m,ans=-inf;
int mp[maxn][maxn],ri[maxn][maxn],le[maxn][maxn],up[maxn][maxn];
int main(){std::ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){cin>>mp[i][j];if(mp[i][j]) le[i][j]=ri[i][j]=j,up[i][j]=1;}}for(int i=1;i<=n;++i){for(int j=2;j<=m;++j){if(mp[i][j] && mp[i][j-1]) le[i][j]=le[i][j-1];}for(int j=n-1;j>=1;--j){if(mp[i][j] && mp[i][j+1]) ri[i][j]=ri[i][j+1];}}for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){if(i>1 && mp[i][j] && mp[i-1][j]){le[i][j]=max(le[i][j],le[i-1][j]);ri[i][j]=min(ri[i][j],ri[i-1][j]);up[i][j]=up[i-1][j]+1;}if(mp[i][j]){int a=ri[i][j]-le[i][j]+1;a=min(a,up[i][j]);ans=max(ans,a);}}}cout<<ans<<endl;return 0;
}
这篇关于动态规划——悬线法 （P1169 棋盘制作 p4147 玉蟾宫 p2701 巨大的牛棚 p1387 最大正方形）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
