动态规划——悬线法 (P1169 棋盘制作 p4147 玉蟾宫 p2701 巨大的牛棚 p1387 最大正方形)

本文主要是介绍动态规划——悬线法 (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 最大正方形)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/830187

相关文章

Android 悬浮窗开发示例((动态权限请求 | 前台服务和通知 | 悬浮窗创建 )

《Android悬浮窗开发示例((动态权限请求|前台服务和通知|悬浮窗创建)》本文介绍了Android悬浮窗的实现效果,包括动态权限请求、前台服务和通知的使用,悬浮窗权限需要动态申请并引导... 目录一、悬浮窗 动态权限请求1、动态请求权限2、悬浮窗权限说明3、检查动态权限4、申请动态权限5、权限设置完毕后

Java使用POI-TL和JFreeChart动态生成Word报告

《Java使用POI-TL和JFreeChart动态生成Word报告》本文介绍了使用POI-TL和JFreeChart生成包含动态数据和图表的Word报告的方法,并分享了实际开发中的踩坑经验,通过代码... 目录前言一、需求背景二、方案分析三、 POI-TL + JFreeChart 实现3.1 Maven

Java导出Excel动态表头的示例详解

《Java导出Excel动态表头的示例详解》这篇文章主要为大家详细介绍了Java导出Excel动态表头的相关知识,文中的示例代码简洁易懂,具有一定的借鉴价值,有需要的小伙伴可以了解下... 目录前言一、效果展示二、代码实现1.固定头实体类2.动态头实现3.导出动态头前言本文只记录大致思路以及做法,代码不进

vue基于ElementUI动态设置表格高度的3种方法

《vue基于ElementUI动态设置表格高度的3种方法》ElementUI+vue动态设置表格高度的几种方法,抛砖引玉,还有其它方法动态设置表格高度,大家可以开动脑筋... 方法一、css + js的形式这个方法需要在表格外层设置一个div,原理是将表格的高度设置成外层div的高度,所以外层的div需要

SpringBoot实现动态插拔的AOP的完整案例

《SpringBoot实现动态插拔的AOP的完整案例》在现代软件开发中,面向切面编程(AOP)是一种非常重要的技术,能够有效实现日志记录、安全控制、性能监控等横切关注点的分离,在传统的AOP实现中,切... 目录引言一、AOP 概述1.1 什么是 AOP1.2 AOP 的典型应用场景1.3 为什么需要动态插

VUE动态绑定class类的三种常用方式及适用场景详解

《VUE动态绑定class类的三种常用方式及适用场景详解》文章介绍了在实际开发中动态绑定class的三种常见情况及其解决方案,包括根据不同的返回值渲染不同的class样式、给模块添加基础样式以及根据设... 目录前言1.动态选择class样式(对象添加:情景一)2.动态添加一个class样式(字符串添加:情

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R

如何提高Redis服务器的最大打开文件数限制

《如何提高Redis服务器的最大打开文件数限制》文章讨论了如何提高Redis服务器的最大打开文件数限制,以支持高并发服务,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录如何提高Redis服务器的最大打开文件数限制问题诊断解决步骤1. 修改系统级别的限制2. 为Redis进程特别设置限制

如何用Python绘制简易动态圣诞树

《如何用Python绘制简易动态圣诞树》这篇文章主要给大家介绍了关于如何用Python绘制简易动态圣诞树,文中讲解了如何通过编写代码来实现特定的效果,包括代码的编写技巧和效果的展示,需要的朋友可以参考... 目录代码:效果:总结 代码:import randomimport timefrom math

使用Python制作一个PDF批量加密工具

《使用Python制作一个PDF批量加密工具》PDF批量加密‌是一种保护PDF文件安全性的方法,通过为多个PDF文件设置相同的密码,防止未经授权的用户访问这些文件,下面我们来看看如何使用Python制... 目录1.简介2.运行效果3.相关源码1.简介一个python写的PDF批量加密工具。PDF批量加密