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

2024-03-20 17:18
文章标签 动态 规划 最大 制作 棋盘 悬线法 玉蟾 巨大 正方形 牛棚 p1387 p1169 p4147 p2701

本文主要是介绍动态规划——悬线法 （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。

相关文章

大语言模型（LLMs）能够进行推理和规划吗？

大语言模型（LLMs）能够进行推理和规划吗？

大语言模型（LLMs），基本上是经过强化训练的 n-gram 模型，它们在网络规模的语言语料库（实际上，可以说是我们文明的知识库）上进行了训练，展现出了一种超乎预期的语言行为，引发了我们的广泛关注。从训练和操作的角度来看，LLMs 可以被认为是一种巨大的、非真实的记忆库，相当于为我们所有人提供了一个外部的系统 1（见图 1）。然而，它们表面上的多功能性让许多研究者好奇，这些模型是否也能在通常需要系
阅读更多...
【杂记-浅谈DHCP动态主机配置协议】

【杂记-浅谈DHCP动态主机配置协议】

DHCP动态主机配置协议 一、DHCP概述1、定义2、作用3、报文类型 二、DHCP的工作原理三、DHCP服务器的配置和管理 一、DHCP概述 1、定义 DHCP，Dynamic Host Configuration Protocol，动态主机配置协议，是一种网络协议，主要用于在IP网络中自动分配和管理IP地址以及其他网络配置参数。 2、作用 DHCP允许计算机和其他设备通
阅读更多...
JavaWeb系列六: 动态WEB开发核心(Servlet) 上

JavaWeb系列六: 动态WEB开发核心(Servlet) 上

韩老师学生 官网文档为什么会出现Servlet什么是ServletServlet在JavaWeb项目位置Servlet基本使用Servlet开发方式说明快速入门- 手动开发 servlet浏览器请求Servlet UML分析Servlet生命周期GET和POST请求分发处理通过继承HttpServlet开发ServletIDEA配置ServletServlet注意事项和细节 Servlet注
阅读更多...
使用XmlPullParser制作BindView工具

使用XmlPullParser制作BindView工具

在之前我写过了一个BindView的工具，之前使用的最要是正则表达的文本分析做的。最近，工作我认识了Android的XML解析，我又想起了这个问题。发现这个问题，其实用XmlPullParser更好解决。所以我重新写了这个工具。简单多了，而且不用格式化代码。 先分析一下如何写，简易思路如下 Created with Raphaël 2.1.0 输入文本路径 读取x
阅读更多...
IPD推行成功的核心要素（十一）技术规划与平台规划促进公司战略成功

IPD推行成功的核心要素（十一）技术规划与平台规划促进公司战略成功

随着外部大环境的影响，各企业仅有良好的愿望是不够的。预测并顺应新兴市场和技术的变化，变危机为转机，不断推出强大的产品才是一个公司持续繁荣的根本保障。而高效的产品开发往往是基于某些关键技术，针对市场推出的一个或几个产品系列，这些产品系列通常共用一些产品平台，共用一种或者几种关键技术。当一家企业进入了平稳发展期，已经建立了较为完善的管理制度和产品开发流程，但是依然认为竞争对手是那样强大，那样不可战胜。
阅读更多...
OSG学习：LOD、数据分页、动态调度

OSG学习：LOD、数据分页、动态调度

LOD（level of detail）：是指根据物体模型的结点在显示环境中所处的位置和重要度，决定物体渲染的资源分配，降低非重要物体的面数和细节度，从而获得高效率的渲染运算。在OSG的场景结点组织结构中，专门提供了场景结点osg::LOD来表达不同的细节层次模型。其中，osg::LOD结点作为父节点，每个子节点作为一个细节层次，设置不同的视域，在不同的视域下显示相应的子节点。 数据分页：在城市
阅读更多...
算法9—两个巨大正整数相加

算法9—两个巨大正整数相加

两个巨大整数相加，可能会造成溢出，或者它的大小已经超出基本数据类型的范围，所以，我们对巨大整数进行相加时，可以把它们转换成字符串，然后通过字符串的处理进行整数相加。 这里有两种做法：第一种，把整数存在一个字符数组里进行处理。代码如下： [java]  view plain copy public static String addThroughArray(String
阅读更多...
Java代理-动态字节码生成代理的5种方式

Java代理-动态字节码生成代理的5种方式

上篇讲到了代理模式出现的原因，实现方式以及跟其他相似设计模式的区别。传送门@_@ http://blog.csdn.net/wonking666/article/details/79497547 1.静态代理的不足 设计模式里面的代理模式，代理类是需要手动去写的。但是手写代理的问题颇多 1.如果不同类型的目标对象需要执行同样一套代理的逻辑，比如说在方法调用前后打印参数和结果，那么仍然需要为每
阅读更多...
关于修改计算机的处理器数和最大内存数的问题

关于修改计算机的处理器数和最大内存数的问题

问题描述： 刚开始本来是想让计算机的运行速度运行的快点，于是在网上搜索如何让计算机的运行速度更快，找到了一种关于修改计算机内存数和计算机的处理核数可以让计算机运行的更快。 遇到问题： 当我通过命令msconfig →引导→高级选项→勾选了处理器数和最大内存数，然后重启，结构整个计算机都卡的要死，于是记录下来。网上的答案有时候真的是很不负责任，也有可能是自己技术不到位。 结果：取消处理器和内
阅读更多...
Linux RedHat 利用 ISO镜像文件制作本地 yum源

Linux RedHat 利用 ISO镜像文件制作本地 yum源

优质博文：IT-BLOG-CN 【1】创建iso存放目录和挂载目录 [root@desktop ~]# cd /mnt/[root@desktop mnt]# mkdir cdrom 【2】将ISO镜像文件挂载到/mnt/cdrom文件夹下（前提你的CD/DVD中有你的ISO文件-安装时使用的镜像文件） mount /dev/cdrom /mnt/cdrom 【3】编辑/et
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2