动态规划——悬线法 （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。

相关文章

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

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

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

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

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

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

《使用Python制作一个PDF批量加密工具》PDF批量加密‌是一种保护PDF文件安全性的方法,通过为多个PDF文件设置相同的密码,防止未经授权的用户访问这些文件,下面我们来看看如何使用Python制... 目录1.简介2.运行效果3.相关源码1.简介一个python写的PDF批量加密工具。PDF批量加密
阅读更多...
Java中JSON字符串反序列化(动态泛型)

Java中JSON字符串反序列化(动态泛型)

《Java中JSON字符串反序列化(动态泛型)》文章讨论了在定时任务中使用反射调用目标对象时处理动态参数的问题,通过将方法参数存储为JSON字符串并进行反序列化,可以实现动态调用,然而,这种方式容易导... 需求：定时任务扫描，反射调用目标对象，但是，方法的传参不是固定的。方案一：将方法参数存成jsON字
阅读更多...
.NET利用C#字节流动态操作Excel文件

.NET利用C#字节流动态操作Excel文件

《.NET利用C#字节流动态操作Excel文件》在.NET开发中,通过字节流动态操作Excel文件提供了一种高效且灵活的方式处理数据,本文将演示如何在.NET平台使用C#通过字节流创建,读取,编辑及保... 目录用C#创建并保存Excel工作簿为字节流用C#通过字节流直接读取Excel文件数据用C#通过字节
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...
软考系统规划与管理师考试证书含金量高吗？

软考系统规划与管理师考试证书含金量高吗？

2024年软考系统规划与管理师考试报名时间节点： 报名时间：2024年上半年软考将于3月中旬陆续开始报名 考试时间：上半年5月25日到28日，下半年11月9日到12日 分数线：所有科目成绩均须达到45分以上（包括45分）方可通过考试 成绩查询：可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间：预计在11月左右 证书领取时间：一般在考试成绩公布后3~4个月，各地领取时间有所不同
阅读更多...
poj 3723 kruscal，反边取最大生成树。

poj 3723 kruscal，反边取最大生成树。

题意： 需要征募女兵N人，男兵M人。 每征募一个人需要花费10000美元，但是如果已经招募的人中有一些关系亲密的人，那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度，征募某个人的费用是10000 - （已经征募的人中和自己的亲密度的最大值）。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析： 先设想无向图，在征募某个人a时，如果使用了a和b之间的关系
阅读更多...
poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976： 题意： 在n场考试中，每场考试共有b题，答对的题目有a题。 允许去掉k场考试，求能达到的最高正确率是多少。 解析： 假设已知准确率为x，则每场考试对于准确率的贡献值为： a - b * x，将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码： #include <iostream>#include <cstdio>#incl
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2