特殊类型动归--区间动归与环形动归

2023-11-19

区间动归

“某类有序事件中前若干个事件的子答案”不能再支撑状态转移,我们需要去寻找“从某个元素起到另一个元素结束所包含所有的(连续)元素的子答案”作为状态。

可以想象,在这个描述下,每个状态会对应于原题序列上的一个区间。区间具有良好的性质:短的区间可以拓宽成长的区间,相同长度的区间互相不包含。这样,可以把所有状态理解成DAG,即不会有可以互相到达的局面。

像这样以区间左右端点来描述状态,一个状态由比它更小的其他状态转移而来的动归,称为“区间动归”。转移时要考虑边界上的变化。边界条件一般是最小单位的区间(即i=j的情况下)。

例题1:石子合并弱化版

有 n 堆石子堆放在路边,现要将石子有序地合并成一堆,规定每次只能移动相邻的两堆石子合并,合并花费为新合成的一堆石子的数量。求将这 N 堆石子合并成一堆的总花费(最小或最大)。
样例输入
5
1 2 3 4 5
样例输出
33

【问题解析】

首先,列出石子 进行观察。A[i]为该堆中的石子个数

 1.□  2.□□ 3.□□□ 4.□□□□ 5.□□□□□
 1.若石子有1堆,则无需合并,花费为0
 2.若石子有2堆,则合并二者,花费为A[0]+A[1]
 3.若石子有3堆,则有2种情况,①先合并A[0]、A[1]再与A[2]合并 ②先合并A[1]、A[2]再与A[0]合并
 4.若石子有4堆,则有3种情况,...............

 总之,在n堆中,有n-1种情况,而最后一次合并总是以某两堆合成一堆为结果。
 即可将n堆划分成A[0...k] 与 A[k+1...n-1]合并, 
 而A[0...k] 与 A[k+1...n-1]已是最优花费,由各自向下分解所得。假设有5堆石子,则A[0...k] 与 A[k+1...n-1]的长度堆数可能为 1、4 。 2、3  。 3、2  。 4、1
 只要其各自已为最优花费。

 以上为递推向下的逻辑,在动态规划是由下而上,即5堆石子 需要长度为 2 3 4 的石子最优花费

在这里插入图片描述
然后开始分析算法过程,首先,最外层循环 控制石子堆长度(len=2 to n),因为只有1堆时无需下续步骤
接着第二层循环,确定石子堆的起始堆号(i=0 to n-len)即为图中的下划线个数。
继续分析,发现还需要一层循环控制更新 A[0…k] 与 A[k+1…n-1]的花费price (k=i to j-1)
确定无遗漏后,开始编写代码过程,如下。
(注意,花费是每两两合并完的石子数依次相加,所以最后一次合并为合并堆数的总石子量)
由sum[i][j]表示第i堆石子到第j堆石子全部合并的总石子量。dp[i][j]为第i堆石子到第j堆合并的花费(随着动态规划的进行,会越来越越接近最优花费)dp[i][i]=0 (本身无需合并,不需花费)
即若仅两堆石子合并 则dp[i][j]=dp[i][i]+dp[j][j]+sum[i][j] = 0+0+sum[i][j]
在这里插入图片描述
归纳总结
( 1 )建立最优值递归式
设 Min [i][j] 代表从第 i 堆石子到第 j 堆石子合并的最小花费, Min [i][k] 代表从第 i 堆石子到第 k 堆石子合并的最小花费,Min[k+1][j] 代表从第 k+1 堆石子到第 j 堆石子合并的最小花费, w ( i , j )代表从 i 堆到 j 堆的石子数量之和。列出递归式:
Min [ i ][ j ] = 0 (i = j)
Min [ i ][ j ] = min ( Min [ i ][ k ] + Min [ k + 1][ j ] + w ( i , j )) , i < j( i ≤ k < j)
Max [i][j] 代表从第 i 堆石子到第 j 堆石子合并的最大花费,Max [i][k] 代表从第 i 堆
石子到第 k 堆石子合并的最大花费,Max [k+1][j] 代表从第 k+1 堆石子到第 j 堆石子合并的最大花费, w ( i , j )代表从 i 堆到 j 堆的石子数量之和。列出递归式:

Max [ i ][ j ] = 0 (i = j)
Max [ i ][ j ] =max( Max [ i ][ k ] + Max [ k + 1][ j ] + w ( i , j )) , i < j ( i ≤ k < j)
二维数组 Min [i][j] 、Max [i][j] 来记录第 i 堆到第 j 堆 a i , a i+1 ,…, a i 堆石子合并的最小花费和最大花费。
( 2 )初始化
输入石子的堆数 n ,然后依次输入各堆石子的数量存储在 a[i] 中,令 Min [i][i]=0 ,
Max [i][i]=0 , sum[0]=0 ,计算 sum[i] ,其中 i= 1 , 2 , 3 ,…, n 。
( 3 )循环阶段
• 按照递归式计算 2 堆石子合并 {a i , a i+1 } 的最小花费和最大花费, i=1 , 2 , 3 ,…, n−1 。
• 按照递归式计算 3 堆石子合并 {a i , a i+1 , a i+2 } 的最小花费和最大花费, i=1 , 2 , 3 ,…,n−2 。

#define M 101
#define INF 1000000000
int n,f[M][M],sum[M][M],stone[M];
int main()
{
	int i,j,k,t;
	cin>>n;
	for(i=1;i<=n;i++)
		scanf("%d",&stone[i]);

	for(i=1;i<=n;i++)
	{
		f[i][i]=0;
		sum[i][i]=stone[i];
		for(j=i+1;j<=n;j++)
			sum[i][j]=sum[i][j-1]+stone[j];
	}
for(int len=2;len<=n;len++)//归并的石子长度
	{
		for(i=1;i<=n-len+1;i++)//i为起点,j为终点
		{
			j=i+len-1;
			f[i][j]=INF;
			for(k=i;k<=j-1;k++)
			{
					 f[i][j]=min(f[i][k]+f[k+1][j])+sum[i][j];
			}
		}
	}
	printf("%d/n",f[1][n]);  
	return 0;
}
	

环形动归

例题:石子合并
在加上环形的限制条件下,其实只需要将环在某一点切断,变成线性来处理。
可以证明一定存在一个“断点”在某两个相邻的石子中间,对于任意环上的合并方式,都不会跨越这个断点进行合并。因此,可以将这个环破成一个链来处理。
如果每次从环中生成一个新的链,分别进行DP,则时间复杂度无法接受。所以可以将这个序列复制一次,变成长度为2N的序列。其中每一个长度为N的连续子序列都是剪开的一条链。剩下的事情和上面一样啦。
代码实现时,长度还是从1枚举到N,但原始链的长度扩大一倍。

#include<bits/stdc++.h>
using namespace std;
#define maxn 205
#define inf 0x7f7f7f7f
int a[maxn],sum[maxn]={0};
int f1[maxn][maxn],f2[maxn][maxn];
int n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[i+n]=a[i];
	}
	for(int i=1;i<=n*2;i++)
		sum[i]=sum[i-1]+a[i];
	memset(f1,0,sizeof(f1));
	//memset(f2,inf,sizeof(f2));

	for(int L=2;L<=n;L++)
		for(int i=1;i+L-1<=n*2;i++)
		{
			int j=i+L-1;
			f2[i][j]=inf;
			for(int k=i;k<j;k++)
			{
				f1[i][j]=max(f1[i][j],f1[i][k]+f1[k+1][j]+sum[j]-sum[i-1]);
				f2[i][j]=min(f2[i][j],f2[i][k]+f2[k+1][j]+sum[j]-sum[i-1]);
			}
				
		}
	int ans1=-inf;
	int ans=inf;
	
	
	for(int i=1;i<=n;i++) ans1=max(ans1,f1[i][i+n-1]);
	for(int i=1;i<=n;i++) ans=min(ans,f2[i][i+n-1]);
	cout<<ans<<endl<<ans1;
	
}

课后练习

1、回文字串
2、道路游戏
3、能量项链

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

特殊类型动归--区间动归与环形动归 的相关文章

随机推荐

  • CentOs7.4 搭建 svn HTTP服务器

    一 通过yum安装svn yum y install mod dav svn yum y install subversion 通过如下命令查看svn 的安装位置 rpm ql subversion 二 创建版本目录库 此仅为目录 为后面创
  • 简单LSTM代码讲解

    仅供本人参考 错了概不负责 part1 图源 https www zhihu com question 41949741 answer 309529532 我们在使用tf nn rnn cell BasicLSTMCell时 有一个要自己设
  • STM32定时器系列 - STM32定时器输出比较

    STM32 定时器除了基本计数定时功能外 还对外扩展了输入 输出通道 从而可以实现输入捕获 比较输出功能 比较输出 Compare Output 功能 定时器通过对预设的比较值与定时器的值做匹配比较之后 并依据相应的输出模式从而实现各类输出
  • 大数据面试题及答案

    Hadoop 相关试题 Hive 相关试题 1 hive表关联查询 如何解决数据倾斜的问题 倾斜原因 map输出数据按key Hash的分配到reduce中 由于key分布不均匀 业务数据本身的特点 建表时考虑不周 等原因造成的reduce
  • 如何快速检测代理IP质量?方法与工具全干货

    一直以来 IP代理都是出海跨境业务的刚需 质量好的IP代理 除了在跨境业务产生巨大作用 在SEO监控 爬虫抓取 市场研究等领域也发挥着很大的作用 但是 对于IP代理的质量检测是我们选择高标准IP代理的一句 我们一般都会建议在使用IP代理前
  • 5G技术优势

    1G实现了移动通话 2G实现了短信 数字语音和手机上网 3G带来了基于图片的移动互联网 而4G则推动了移动视频的发展 5G网络则视为未来物联网 车联网等万物互联的基础 同时 5G普及将使得包括虚拟现实和增强现实这些技术成为主流 4G网络是专
  • 修改网页logo

    在用浏览器打开网站的时候 浏览器标签页上面有网站的图标 类似于logo小图标 如下图 步骤1 打开你的tomcat的安装目录 我的目录实在G盘 G apache tomcat 7 0 53 windows x64 apache tomcat
  • java进制转换方法

    一 十进制向二 八 十六进制的转换 方法一 Integer toBinaryString i 表示十进制转为二进制 Integer toOctalString i 表示十进制转为八进制 Integer toHexString i 表示十进制
  • 周庄不买门票攻略_周庄古镇旅游攻略

    周庄古镇旅游攻略 周庄古镇是世界文化遗产预选地 首批国家5A级旅游景区 位于苏州城东南 位于昆山 吴江 上海三地交界处 周庄古镇四面环水 因河成镇 依水成街 以街为市 井字型河道上完好保存着14座建于元 明 清各代的古石桥 800多户原住民
  • org/springframework/boot/maven/RepackageMojo has been compiled by a more recent version of the Java

    项目场景 项目中执行clean 再执行install时报错 错误如下 org springframework boot maven RepackageMojo has been compiled by a more recent versi
  • Python库之自然语言处理和文本挖掘

    来源地址 http www python88 com topic 37015 https mp weixin qq com s sPAomFg 5JZigFUG CtnaQ 自然语言处理和文本挖掘库主要用于以自然语言文本为对象的数据处理和建
  • linux基本命令练习

    1 列出 etc目录下的所有文件名称 2 创建文件file1 和file2 并复制到 home目录下 3 显示以ma开头的所有命令 ma 双击两次 TAB键 4显示所有文件名中有 bash的文件 用tab命令补全 5 显示当前所在的目录路径
  • android图像识别(百度普通物体识别)

    android图像识别 采用百度sdk 识别准确率基本上能用 主要缺陷是百度sdk免费额度有限 demo链接如下 仅供参考https download csdn net download android xc 12274161
  • Python进阶之CrawlSpider的应用及Scrapy配置项的引用

    1 CrawlSpider的应用 CrawlSpider可以根据规则自动分析链接的数据并按照正则的要求取出需要的数据 scrajpy startproject yg cd yg 注意 t crawl参数 scrapy genspider t
  • 解决SqlServer批量插入最多2100条数据的方法

    SqlServer批量插入数据时最多不能超过2100条 记录一下解决办法 Java代码 public void batchInsert List
  • 基于vue实现移动端点击上方导航,内容滑动切换,滑动内容导航自动切换。

    这是在日常开发过程中常见的选项卡 带滑动切换效果 小白一枚 不足之处还望体谅 包涵 这也是第一次尝试写博客 以后会继续分享一些工作中的问题与收获 实现效果 点击上方导航 当前导航添加样式 下方内容滑动切换 滑动下方内容上面导航切换 第一步
  • 论文笔记:Region Representation Learning via Mobility Flow

    2017 CIKM 1 摘要和介绍 使用出租车出行数据学习区域向量表征 同时考虑时间动态和多跳位置转换 gt 通过flow graph和spatial graph学习表征 出租车交通流可以作为区域相似度的一种 A区域和B区域之间流量大 gt
  • JS 变量提升和函数提升

    变量提升 这里介绍一个变量提升提升的经典案例 for var i 0 i lt 10 i setTimeout gt console log i 1000 这里打印是10个10 因为在执行第一个setTimeout时 Js不会等待1秒后再去
  • 怎么解决“无法打开包括文件:“graphics.h”: No such file or directory”的问题

    在接手同伴的中国象棋项目时 导入项目后 发现VS一直提示 无法打开包括文件 graphics h No such file or directory 在查阅资料后发现是缺少easyx文件 接下来 就介绍一下手动配置一下easyx文件 eas
  • 特殊类型动归--区间动归与环形动归

    区间动归 某类有序事件中前若干个事件的子答案 不能再支撑状态转移 我们需要去寻找 从某个元素起到另一个元素结束所包含所有的 连续 元素的子答案 作为状态 可以想象 在这个描述下 每个状态会对应于原题序列上的一个区间 区间具有良好的性质 短的