首页 > 其他分享 >插入类型 DP 学习笔记

插入类型 DP 学习笔记

时间：2024-08-30 16:39:02浏览次数：13  
标签：ai dpi 笔记 插入 DP 1i iii dp

插入类型 DP

形式

  • 多为 nnn 个元素无法重复使用，需要给定一个排列，满足一定条件或是求有多少个排列满足一定条件。

  • nnn 一般在 100∼5×103100 \sim 5 \times 10^3100∼5×103 左右。

  • 满足一些函数图像，类似于波浪函数，且答案与每个波浪和波浪的顶点有关（函数的 xxx 坐标为下标，yyy 坐标为下标上数的值）。

满足以上三个条件的 DP 大部分是插入类型的 DP。

引入

先来看一道例题：

  • 对于一个正整数序列 aaa，长度为 n(n≥3)n(n \ge 3)n(n≥3)，如果对于所有的 2≤i≤n−12 \le i \le n-12≤i≤n−1，都有 ai−1+ai+1≥2aia_{i-1}+a_{i+1}\ge 2a_iai−1​+ai+1​≥2ai​，就称这个序列是“美丽的”。现在给你另一个正整数序列 bbb，问你有多少种排列这个序列的方式使得这个序列是美丽的。（n≤100n \le 100n≤100）

这道例题看似无从下手，但是我们把式子变换一下可以发现：

ai−1+ai+1≥2ai→ai−1−ai≥ai−ai+1a_{i-1}+a_{i+1} \ge 2a_i \to a_{i-1}-a_i \ge a_i-a_{i+1}ai−1​+ai+1​≥2ai​→ai−1​−ai​≥ai​−ai+1​

即差分递增，差分递增有什么好处呢？把所有满足条件的 aaa 序列列举出来，就会发现它其实是先是一段递减，然后中间可能会有平的一段（差分为 000），最后一段递增。事实上就是一个有平台的单谷函数。

有了这个性质，我们按 aaa 从小到大排序，然后依次插入进这个函数，每个数可以插入到函数的左边，或者右边。（因为已经排好序了）

于是设 dpi,j,k,ldp_{i,j,k,l}dpi,j,k,l​ 表示左边为 i,ji,ji,j 且 右边为 k,lk,lk,l 的方案数总和。

注意观察：这个 DP 没有后效性，且能够顺利转移，满足子问题包含的性质。

综上，可以 O(n4)O(n^4)O(n4) 解决。

实践

容易看出，引子是一个水题，因为我们还没有牵扯到其它的限制，只是规定元素不能重复选，接下来我们看一下这道题：

CEOI2016-kangaroo

这道题就满足了上面三条形式：

  • nnn 个元素无法重复使用，求有多少个排序满足一定条件。

  • 2≤n≤2×1032 \le n \le 2\times 10^32≤n≤2×103

  • 波浪函数，每个波浪的长度为 111

这个时候，考虑怎么转换已经没有用了，因为它并不满足类似于差分递增这种规律，使得有一个单调性在里面，所以我们按照这三条形式的最后一条，即波浪进行入手。

先看下面一幅图：

（如图，这是n=6,s=4,t=5n=6,s=4,t=5n=6,s=4,t=5 时候的一种情况。其中 yyy 轴代表点的编号，xxx 轴代表访问的顺序，即从 111 访问到 nnn）

那么我们观察到这个函数图像有 555 段（因为每段必须长度为 111）。段长不好设计 DP，那我们考虑用段的个数来设计 DP。

这种类型的 DP，有几个要素：

  • 确定元素添加顺序
  • 确定状态的转移
  • 确定对于 s,ts,ts,t 的特判

我们一个问题一个问题解决。

确定元素添加顺序

没什么好说的，既然是排列，那就要从 1∼n1\sim n1∼n 挨个添加。

确定状态转移

因为必须在 O(n2)O(n^2)O(n2) 时间内通过此题，所以设 dpi,jdp_{i,j}dpi,j​ 表示从 1∼i1 \sim i1∼i 中，分成了 jjj 段的方案数，容易得知，最后的答案是 dpn,1dp_{n,1}dpn,1​。

什么叫段数，请看这幅图：

这里，就是把 1∼51 \sim 51∼5 分成了两段：A∼D,F∼FA \sim D,F \sim FA∼D,F∼F。

因为我们的 sss 需要特判，所以把它归在 B∼DB \sim DB∼D 这个段里，准确的说，每个段应该是类似于 MMM 形的（可以有很多拐弯，但是第一个是上升，最后一个下降）。为了准确计算，sss 和 ttt 都并到相邻的段里面。

考虑转移，因为我们选择了 1∼n1\sim n1∼n 这种顺序，那么我们每个 iii 都是在选了比它更小的数之后决策，再加上每个段是 MMM 形状，所以 iii 可以把两个段合并成一个，或者自己新开一个段。

综上，DP 方程就可以出来了：

dpi,j={dpi−1,j+dpi−1,j−1i=s or i=tjdpi−1,j+1+(j−[i>s]−[i>t])dpi−1,j−1other wisedp_{i,j} = \begin{cases} dp_{i-1,j}+dp_{i-1,j-1} & i=s \text{ or } i=t\\ jdp_{i-1,j+1}+(j-[i>s]-[i>t])dp_{i-1,j-1} & \text{other wise} \end{cases}dpi,j​={dpi−1,j​+dpi−1,j−1​jdpi−1,j+1​+(j−[i>s]−[i>t])dpi−1,j−1​​i=s or i=tother wise​

总述一下，这种类型的题其实大部分都是对段进行 DP，然后考虑转移和特判，之后就可以过了。

小结

此类 DP 被称为 “插入DP” 或者是 “连续段DP”，主要都是依据段数来转移状态。

模型：1∼n1 \sim n1∼n 的元素不能重复使用，按照某个顺序排列 i,ji,ji,j 能够使得 i,ji,ji,j 的贡献成为定值。

不同之处：有些题目固定了左右两端点，有些题目没有固定左右两端点。

依据题目的不同要求，大部分题目中的段是可以 A,W,V,MA,W,V,MA,W,V,M 等形状的，但少部分题目（例题）则限制了形状，但归根结底转移都是一样的套路。

设计转移时通常 按照一定顺序插入，且知道了这个顺序就知道了题目中要求的函数的值（函数的值是根据数的一定顺序决定的） 且 每个元素只有合并两段、接续一段、新开一段等操作，这样才能更好的帮助我们维护 DP 数组。（有些时候元素插入在一段的左/右边的结果不一样，需要再开一维）

推这种 DP 式子的时候，我们会发现有些情况可能会缠在一起，让人分不清楚。这里要着重说一下：每个状态其实都是在为后面的状态作准备。

比如：

明明可以写为接在一个段的后面，DP 方程中偏要写为新开一个段。这就是因为新开一个段能够保证这个元素的左右两边都是比它大的数，如果是接续一个段，那么只能保证一端比它大，一端比它小。

所以，我们对于新开一个段和接续一个段的状态会不会重复的问题，只需要考虑它们最后形成的状态会不会重复就行了，而并不需要考虑当前的形态相不相同。例如：1,3,2,41,3,2,41,3,2,4 中如果 444 是接续的 222 后面，那最后就有可能是 1,3,2,4,⋯1,3,2,4,\cdots1,3,2,4,⋯，即 2,42,42,4 中间不会有任何元素；如果 444 是新开了一个段，那么最后就可能是 1,3,2,⋯ ,4,⋯1,3,2,\cdots,4,\cdots1,3,2,⋯,4,⋯。那有些人就会有问题：如果 222 后面的省略号的内容为空的话，那不就相同了吗？不会，因为这样的话，因为 4,24,24,2 不在一个段，所以这里至少有两段，而我们最终统计答案的时候是只统计 111 段的，意思是中间至少有一个元素把这两段合并起来，就与最开始的假设矛盾了，故状态不会重复。

最后，特别要注意整个序列两个端点需要特别判断，处理这种类型的方法有两种：

  • 在转移过程中就把贡献去掉/加上。（多为题目固定了左右两端点）
  • 多开两维数组记录两个端点的贡献或一些信息。（多为题目没有固定左右两端点）

习题

部分习题讲评

CF704B-Ant Man

初探题面

这道题我们可以先转换一下题意：

让 ai←a−i+xi,bi←bi−xi,ci←ci+xi,di←di−xia_i \gets a-i+x_i,b_i \gets b_i-x_i,c_i \gets c_i+x_i,d_i \gets d_i-x_iai​←a−i+xi​,bi​←bi​−xi​,ci​←ci​+xi​,di​←di​−xi​。

那么就可以将 f(i,j)f(i,j)f(i,j) 写为：

f(i,j)={di+aji<jci+bji>jf(i,j) = \begin{cases} d_i+a_j & i<j\\ c_i+b_j & i>j \end{cases}f(i,j)={di​+aj​ci​+bj​​i<ji>j​

由这个公式看出：权值与下标的大小相关，只要确定了下标的大小，那么这个权值基本上就确定了。

所以，按照 1∼n1\sim n1∼n 的顺序插入 DP。

状态设计

还是像例题一样，设 dpi,jdp_{i,j}dpi,j​ 为 1∼i1 \sim i1∼i 中分成 jjj 段最小的代价是多少。

但是与例题不同的是，这里的每一段可以是 V,M,W,AV,M,W,AV,M,W,A 形状的，就是起始位置没有硬性要求。（对于起始位置的要求视题意而设计状态）

那么我们就可以开始 dp 了。

首先考虑一般情况（i≠s and i≠ti \ne s \text{ and } i\ne ti=s and i=t）：

（以下状态设计均考虑费用提前计算技巧）

  • iii 能够把之前的两段拼起来，那么 iii 对于全局权值的贡献就是 ai+cia_i+c_iai​+ci​。
  • iii 能够在一段的末尾与那一段拼起来，那么 iii 对于全局权值的贡献是 ai+dia_i+d_iai​+di​。
  • iii 能够在一段的前面与那一段拼起来，那么 iii 对于全局权值的贡献是 bi+cib_i+c_ibi​+ci​。
  • iii 独立成为一段，则贡献是 bi+dib_i+d_ibi​+di​。

所以对于 i≠s and i≠ti \ne s \text{ and } i \ne ti=s and i=t，转移有四种：

dpi,j=min⁡{dpi−1,j+1+ai+cidpi−1,j+ai+didpi−1,j+bi+cidpi−1,j−1+bi+didp_{i,j} = \min\begin{cases} dp_{i-1,j+1} +a_i+c_i \\ dp_{i-1,j}+a_i+d_i \\ dp_{i-1,j} + b_i+c_i \\ dp_{i-1,j-1}+b_i+d_i \end{cases}dpi,j​=min⎩⎨⎧​dpi−1,j+1​+ai​+ci​dpi−1,j​+ai​+di​dpi−1,j​+bi​+ci​dpi−1,j−1​+bi​+di​​

注意，这些式子是怎么推导出来的！

  • 因为贡献只与两个数的大小有关
  • 两个数的大小这么来判断：比 iii 先填的数一定比 iii 小，比 iii 后填的数一定比 iii 大。

根据这两点，权值和方程就能很轻松写出来了。

至于 i=s or i=ti=s \text{ or } i=ti=s or i=t 的情况，一个是只能加在某一段的后面，一个是只能加在某一段的前面，两个都可以自己成为一段，等待后面的元素把两段拼在一起！

细节

1、对于以 sss 开头的一段，不允许有任何元素拼在前面；对于以 ttt 结尾的一段，不允许有任何元素拼在后面。

2、对于以 sss 开头的一段和以 ttt 开头的一段，一定到最后才能拼起来，不能在前面就合成了一个段。

3、为什么我们合并两个段不需要额外记录是不是 sss 和 ttt 所在的段？因为不管是合并哪两个段事实上是一样的，只要有一个段没有 sss 和 ttt，那么这个合并就可以进行。

4、为什么考虑加在某个段的前面的时候不需要判断 sss，ttt 也不需要判断？因为我们加到任意一段前面/后面的代价是一样的。（都是费用提前计算）

5、做这类题目时，一定要把 iii 和 jjj 的关系分开（常用方法：费用提前计算），不然无法记录状态！

综上，这道题目就做完了，为了避免一些特殊情况，代码采用从前往后的方式 DP。（从后往前也可以）

#include<bits/stdc++.h>
#define ll long long
#define N 5005
using namespace std;
ll n,i,j,x[N],a[N],b[N],c[N],d[N],s,t,dp[N][N];
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>s>>t;
	for(i=1;i<=n;i++) cin>>x[i];
	for(i=1;i<=n;i++) cin>>a[i],a[i]+=x[i];
	for(i=1;i<=n;i++) cin>>b[i],b[i]-=x[i];
	for(i=1;i<=n;i++) cin>>c[i],c[i]+=x[i];
	for(i=1;i<=n;i++) cin>>d[i],d[i]-=x[i];
	memset(dp,0x3f,sizeof(dp));
	dp[0][0] = 0;
	for(i=1;i<=n;i++){
		for(j=0;j<i;j++){
			if(i==s){
				if(j>=(i>t)){
					if(j) dp[i][j] = min(dp[i][j],dp[i-1][j]+c[i]);
					dp[i][j+1] = min(dp[i][j+1],dp[i-1][j]+d[i]);
				}
			}
			else if(i==t){
				if(j>=(i>s)){
					if(j) dp[i][j] = min(dp[i][j],dp[i-1][j]+a[i]);
					dp[i][j+1] = min(dp[i][j+1],dp[i-1][j]+b[i]);
				}
			}
			else{
				if(j<((i>t)+(i>s))) continue;
				if(j>=2) dp[i][j-1] = min(dp[i][j-1],dp[i-1][j]+a[i]+c[i]);
				dp[i][j+1] = min(dp[i][j+1],dp[i-1][j]+b[i]+d[i]);
				if(j>(i>t)) dp[i][j] = min(dp[i][j],dp[i-1][j]+a[i]+d[i]);
				if(j>(i>s)) dp[i][j] = min(dp[i][j],dp[i-1][j]+b[i]+c[i]);
			}
		}
	}
	cout<<dp[n][1]<<endl;
}

[JOI Open 2016] 摩天大楼

初探题面

首先，看到绝对值想到分类讨论，即为：

g(i,i+1)={fi−fi+1fi≥fi+1fi+1−fifi<fi+1g(i,i+1) = \begin{cases} f_i-f_{i+1} & f_i \ge f_{i+1} \\ f_{i+1}-f_i & f_i < f_{i+1} \end{cases}g(i,i+1)={fi​−fi+1​fi+1​−fi​​fi​≥fi+1​fi​<fi+1​​

那么又是根据大小关系来决定权值大小了，所以考虑插入 DP。

第一种方法

状态推导

像上一道题一样，这里的状态因为没有段长的硬性要求，所以 W,V,A,MW,V,A,MW,V,A,M 形状的段都是可以的，因此也减少了初始和结尾字符的特判（尽管题目也不需要特判）。

设 dpi,j,kdp_{i,j,k}dpi,j,k​ 表示 1∼i1\sim i1∼i 这些数所代表的数值插入进去之后有 jjj 段当前权值总和为 kkk 的情况总数。

注意到最开始是不用 f1−f0f_1-f_0f1​−f0​ 或者 f0−f1f_0-f_1f0​−f1​，结尾同理，所以依旧需要特判。

再发现，如果我们不记录开始和结尾数值的话，很难维护，所以我们要 用尽可能小的空间传递更多的信息。

  • 如果我们能够确定第一个位置是否已经被填了，那么就不存在其它特判情况了，即在填的时候特判一下就可以了。（结尾同理）

根据上面那一条发现的性质，我们对 DP 状态进行修改，设 dpi,j,k,0/1,0/1dp_{i,j,k,0/1,0/1}dpi,j,k,0/1,0/1​ 表示 1∼i1\sim i1∼i 这些数所代表的数值插入进去之后有 jjj 段当前权值总和为 kkk 且开头结尾有没有被确定的情况总数。

这个转移方程一确定，那么事情就简单多了。

转移方程

首先，明确一下状态的后效性如何去除（因为 g(i,i+1)g(i,i+1)g(i,i+1) 与两个元素有关）。

看下面这幅图：

（其中横轴为元素的位置，纵轴为元素的值）

容易看出这样的总的权值和是：∣5−1∣+∣1−6∣+∣6−4∣+∣4−3∣+∣3−2∣+∣2−7∣+∣7−8∣|5-1|+|1-6|+|6-4|+|4-3|+|3-2|+|2-7|+|7-8|∣5−1∣+∣1−6∣+∣6−4∣+∣4−3∣+∣3−2∣+∣2−7∣+∣7−8∣ 的。

在我们按照大小顺序插入的前提下考虑分开：5−1+6−1+6−4+4−3+3−2+7−2+8−75-1+6-1+6-4+4-3+3-2+7-2+8-75−1+6−1+6−4+4−3+3−2+7−2+8−7，消项得：5−1+6−1+6−2+8−25-1+6-1+6-2+8-25−1+6−1+6−2+8−2。

这样我们就可以得知，每个极小值会被减去两次（但是如果是在序列开头或末尾只会被减一次），每个极大值会被加两次（但是如果是在序列开头或末尾只会被加一次）。

即遇到极大值看它是不是在开头或者末尾，如果在，贡献就会一份，否则为两份，极小值同理。

综上，我们就把 i,i+1i,i+1i,i+1 的贡献分开了，而且也利用到了我们知晓元素之间大小关系的性质，DP 转移就可以开始执行了。

以下状态设计均为从大往小插入考虑

然后，熟悉的分类讨论：

  • 对于 iii，它合并了两个段，段数少 111

因为 iii 合并两个段，所以它不能在最左边或者最右边，而且它两端都是比它小的数，那么它便是这个区间的极小值，对全局的贡献是负的两倍。即：

dpi,j,k,p,l=jdpi−1,j+1,k+2ai,p,ldp_{i,j,k,p,l} = jdp_{i-1,j+1,k+2a_i,p,l}dpi,j,k,p,l​=jdpi−1,j+1,k+2ai​,p,l​

（为什么是加 2ai2a_i2ai​，是因为，它插入之后贡献为 kkk，插入之前肯定就是加上）

  • 对于 iii，它新开了一个段，段数多 111

因为 iii 新开了一个段，之后合并它和其它段的数一定比它小，所以它是区间极大值，对全局的贡献是正两倍，注意，它如果是在最左边，它的贡献就只有一倍，在最右边同理。特别注意，如果左右两边已经确定了，那么它能够新开段的位置会少 1∼21\sim 21∼2 个。即：

dpi,j,k,0,0=jdpi−1,j−1,k−2ai,0,0dpi,j,k,0,1=(j−1)dpi−1,j−1,k−2ai,0,1+dpi−1,j−1,k−ai,0,0dpi,j,k,1,0=(j−1)dpi−1,j−1,k−2ai,1,0+dpi−1,j−1,k−ai,0,0dpi,j,k,1,1=(j−2)dpi−1,j−1,k−2ai,1,1+dpi−1,j−1,k−ai,1,0+dpi−1,j−1,k−ai,0,1\begin{aligned} dp_{i,j,k,0,0} &= jdp_{i-1,j-1,k-2a_i,0,0} \\ dp_{i,j,k,0,1} &= (j-1)dp_{i-1,j-1,k-2a_i,0,1}+dp_{i-1,j-1,k-a_i,0,0} \\ dp_{i,j,k,1,0} &= (j-1)dp_{i-1,j-1,k-2a_i,1,0}+dp_{i-1,j-1,k-a_i,0,0} \\ dp_{i,j,k,1,1} &= (j-2)dp_{i-1,j-1,k-2a_i,1,1}+dp_{i-1,j-1,k-a_i,1,0}+dp_{i-1,j-1,k-a_i,0,1} \end{aligned}dpi,j,k,0,0​dpi,j,k,0,1​dpi,j,k,1,0​dpi,j,k,1,1​​=jdpi−1,j−1,k−2ai​,0,0​=(j−1)dpi−1,j−1,k−2ai​,0,1​+dpi−1,j−1,k−ai​,0,0​=(j−1)dpi−1,j−1,k−2ai​,1,0​+dpi−1,j−1,k−ai​,0,0​=(j−2)dpi−1,j−1,k−2ai​,1,1​+dpi−1,j−1,k−ai​,1,0​+dpi−1,j−1,k−ai​,0,1​​
  • 对于 iii，它延续了某个段，并接在该段的左/右边，段数不变

我们以左边为例，因为 iii 在普通情况下一边会有比它小的，一边会有比它大的，所以 iii 对总的值没有贡献，但是当 iii 在左边或者右边时，它是区间极小值，贡献是负一倍。即：

dpi,j,k,0,0=jdpi−1,j,k,0,0dpi,j,k,0,1=jdpi−1,j,k,0,1dpi,j,k,1,0=(j−1)dpi−1,j,k,1,0+dpi−1,j,k+ai,0,0dpi,j,k,1,1=(j−1)dpi−1,j,k,1,1+dpi−1,j,k+ai,0,1\begin{aligned} dp_{i,j,k,0,0} &= jdp_{i-1,j,k,0,0} \\ dp_{i,j,k,0,1} &= jdp_{i-1,j,k,0,1} \\ dp_{i,j,k,1,0} &= (j-1)dp_{i-1,j,k,1,0}+dp_{i-1,j,k+a_i,0,0} \\ dp_{i,j,k,1,1} &= (j-1)dp_{i-1,j,k,1,1}+dp_{i-1,j,k+a_i,0,1} \end{aligned}dpi,j,k,0,0​dpi,j,k,0,1​dpi,j,k,1,0​dpi,j,k,1,1​​=jdpi−1,j,k,0,0​=jdpi−1,j,k,0,1​=(j−1)dpi−1,j,k,1,0​+dpi−1,j,k+ai​,0,0​=(j−1)dpi−1,j,k,1,1​+dpi−1,j,k+ai​,0,1​​

加在右边同理，由此我们推导完了整个 DP，但是实现过程中还要注意一下转移时的细节：左右端点固定后权值是多少？有多少个段可以插入等。

这种方法常数很大，同时不利于优化，但是个人认为思维跟 kangaroo 差不多，而且更好想一些。

第二种方法

此处不再赘述，详见：Afewsuns 的博客-[JOI Open 2016]摩天大楼题解。

注：[ZJOI2012] 波浪 和此题十分相像，主要是处理精度问题和小数的“快速输出”，那道题可能会卡常，推荐使用第二种方法。

此处给出第一种方法的代码：

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll n,i,j,k,l,a[105],dp[2][105][8005][2][2],ans;
bool cmp(ll a,ll b){return a>b;}
void add(ll &a,ll b){
	a += b;
	a %= mod;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>l;
	for(i=1;i<=n;i++) cin>>a[i];
	if(n==1){
		cout<<1<<endl;
		return 0;
	} 
	sort(a+1,a+n+1,cmp);
	dp[0][0][0][0][0] = 1;
	for(i=1;i<=n;i++){
		for(j=0;j<=i;j++) for(k=0;k<=6000;k++) dp[i&1][j][k][0][0]=dp[i&1][j][k][1][0]=dp[i&1][j][k][0][1]=dp[i&1][j][k][1][1]=0;
		for(j=1;j<=i;j++){
			for(k=0;k<=6000;k++){
				//MERGE
				add(dp[i&1][j][k][0][0],j*dp[(i-1)&1][j+1][k+2*a[i]][0][0]);
				add(dp[i&1][j][k][0][1],j*dp[(i-1)&1][j+1][k+2*a[i]][0][1]);
				add(dp[i&1][j][k][1][0],j*dp[(i-1)&1][j+1][k+2*a[i]][1][0]);
				add(dp[i&1][j][k][1][1],j*dp[(i-1)&1][j+1][k+2*a[i]][1][1]);
				if(k>=2*a[i]){
					//NEW
					add(dp[i&1][j][k][0][0],j*dp[(i-1)&1][j-1][k-2*a[i]][0][0]);
					add(dp[i&1][j][k][1][0],(j-1)*dp[(i-1)&1][j-1][k-2*a[i]][1][0]);
					add(dp[i&1][j][k][0][1],(j-1)*dp[(i-1)&1][j-1][k-2*a[i]][0][1]);
					if(j-1>1) add(dp[i&1][j][k][1][1],(j-2)*dp[(i-1)&1][j-1][k-2*a[i]][1][1]);
				}
				if(k>=a[i]){
					//NEW
					add(dp[i&1][j][k][1][0],dp[(i-1)&1][j-1][k-a[i]][0][0]);
					add(dp[i&1][j][k][0][1],dp[(i-1)&1][j-1][k-a[i]][0][0]);
					add(dp[i&1][j][k][1][1],dp[(i-1)&1][j-1][k-a[i]][0][1]+dp[(i-1)&1][j-1][k-a[i]][1][0]);
				}
				//LEFT
				add(dp[i&1][j][k][0][0],j*dp[(i-1)&1][j][k][0][0]);
				if(j>1) add(dp[i&1][j][k][1][0],(j-1)*dp[(i-1)&1][j][k][1][0]);
				add(dp[i&1][j][k][1][0],dp[(i-1)&1][j][k+a[i]][0][0]);
				add(dp[i&1][j][k][0][1],j*dp[(i-1)&1][j][k][0][1]);
				if(j>1) add(dp[i&1][j][k][1][1],(j-1)*dp[(i-1)&1][j][k][1][1]+dp[(i-1)&1][j][k+a[i]][0][1]);
				else add(dp[i&1][j][k][1][1],dp[(i-1)&1][j][k+a[i]][0][1]);
				//RIGHT
				add(dp[i&1][j][k][0][0],j*dp[(i-1)&1][j][k][0][0]);
				add(dp[i&1][j][k][1][0],j*dp[(i-1)&1][j][k][1][0]);
				if(j>1) add(dp[i&1][j][k][0][1],(j-1)*dp[(i-1)&1][j][k][0][1]);
				add(dp[i&1][j][k][0][1],dp[(i-1)&1][j][k+a[i]][0][0]);
				if(j>1) add(dp[i&1][j][k][1][1],(j-1)*dp[(i-1)&1][j][k][1][1]+dp[(i-1)&1][j][k+a[i]][1][0]);
				else add(dp[i&1][j][k][1][1],dp[(i-1)&1][j][k+a[i]][1][0]);
			}
		}
	}
	for(i=0;i<=l;i++) ans=(ans+dp[n&1][1][i][1][1])%mod;
	cout<<ans<<endl;
}

[ABC209F] Deforestation

初探题面

这道题有点类似于前面提到的“凸”这道例题，但是它没有叫你计算最小的花费是多少，而是计算有多少种方案能够达到最小的花费。

遇到这种类型的题目，首先要明确在什么条件下能够达到最小的花费。

因为任意一个 iii 产生的权值与 i−1,i,i+1i-1,i,i+1i−1,i,i+1 有关，说人话就是相邻的元素选择的顺序会影响到它的权值，所以我们考虑对于 i,i+1i,i+1i,i+1，哪个先选比较好。

  • 如果先选 iii，权值为：ai−1+ai+ai+1+ai+1+ai+2a_{i-1}+a_i+a_{i+1}+a_{i+1}+a_{i+2}ai−1​+ai​+ai+1​+ai+1​+ai+2​。
  • 如果先选 i+1i+1i+1，权值为：ai+ai+1+ai+2+ai+ai−1a_i+a_{i+1}+a_{i+2}+a_i+a_{i-1}ai​+ai+1​+ai+2​+ai​+ai−1​。

用第一个式子减去第二个式子得：2ai+1−2ai2a_{i+1}-2a_i2ai+1​−2ai​。

所以当 ai+1>aia_{i+1} > a_iai+1​>ai​ 时，先选 i+1i+1i+1 更好；当 ai>ai+1a_i > a_{i+1}ai​>ai+1​ 时，先选 iii 更好；如果两者相等，那么我们可以任意抉择。

很明显的，对于每组 i,i+1i,i+1i,i+1 我们都可以这么抉择并且至少有一种方案满足这种选择，所以这种局部最优性可以扩展到全局，因此，我们只要求出满足这种顺序的方案数就行了。

状态设计

我们发现如果按照这个关系减出来的图其实是一个 TAG，不好维护插入顺序。因此我们只能考虑从 1∼n1 \sim n1∼n 考虑插入。

因为 iii 可以插入的方案数仅与 i−1i-1i−1 所插入的位置有关系，而且题目允许 O(n2)O(n^2)O(n2) 的空间和时间，因此我们设计两维 DP 数组：dpi,jdp_{i,j}dpi,j​ 表示第 iii 个数插入到了第 jjj 个位置满足条件的方案。

说明一下，这里的第 jjj 个位置并不是最终操作序列上的位置，而是操作序列只保留 1∼i1\sim i1∼i 的子序列的相对位置。

对于 ai>ai−1a_i > a_{i-1}ai​>ai−1​ 先选 iii，所以 iii 的相对位置一定在 i−1i-1i−1 的相对位置的前面，故 dpi,j=∑k=jidpi−1,kdp_{i,j} = \sum_{k=j}^i dp_{i-1,k}dpi,j​=∑k=ji​dpi−1,k​。

对于 ai<ai−1a_i < a_{i-1}ai​<ai−1​ 先选 i−1i-1i−1，所以 iii 的相对位置一定在 i−1i-1i−1 的相对位置的后面，故 dpi,j=∑k=1j−1dpi−1,kdp_{i,j} = \sum_{k=1}^{j-1} dp_{i-1,k}dpi,j​=∑k=1j−1​dpi−1,k​。

对于 ai=ai−1a_i = a_{i-1}ai​=ai−1​ 都可以先选，所以全部情况都可以转移，故 dpi,j=∑k=1j−1dpi−1,kdp_{i,j} = \sum_{k=1}^{j-1} dp_{i-1,k}dpi,j​=∑k=1j−1​dpi−1,k​。

注：

  • 第一个转移方程从 jjj 开始循环到 iii 是因为如果 i−1i-1i−1 在 1∼i−11 \sim i-11∼i−1 的第 jjj 个位置，那么 iii 就可以插入到第 jjj 个位置的前面使得 iii 在 i−1i-1i−1 的前面并且相对位置也是 jjj。
  • 第二个转移方程循环到 j−1j-1j−1 的道理同上。
  • 这种方法为什么能不重不漏，是因为两个不同的最终操作序列一定有一个 iii 在 1∼i1\sim i1∼i 中的相对位置不同；两个相同的最终操作序列一定满足每一个 iii 在 1∼i1\sim i1∼i 中的相对位置相同。
  • 初始化 DP 的时候需要注意 111 在 1∼11\sim 11∼1 中的相对位置只有 111 这一个。

综上，代码就可以写出来了。

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll n,a[4005],dp[4005][4005],m[4005][4005],i,j;
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(i=1;i<=n;i++) cin>>a[i];
	dp[1][1] = 1;
	for(i=1;i<=n;i++) m[1][i]=1;
	for(i=2;i<=n;i++){
		for(j=1;j<=i;j++){
			if(a[i]==a[i-1]) dp[i][j]=m[i-1][i-1];
			if(a[i]>a[i-1]) dp[i][j]=((m[i-1][i-1]-m[i-1][j-1])%mod+mod)%mod;
			if(a[i]<a[i-1]) dp[i][j]=m[i-1][j-1];
		}
		for(j=1;j<=n;j++) m[i][j]=(m[i][j-1]+dp[i][j])%mod;
	}
	cout<<m[n][n]<<endl;
}

CF1515E-Phoenix and Computers

初探题面

一看就知道是插入 DP，但是如何设计状态令人十分难为。

还是想用 dpi,jdp_{i,j}dpi,j​ 表示开了 iii 台，构成了 jjj 个连续段。

根据上面的总结，我们知道，只要这个状态所产生的的最终的所有的状态不会与另外一个不同的状态（同一阶段）所产生的不同的所有的状态相重合，那么这种做法就会做到不重不漏。

而且题目要求如果 i−1i-1i−1，i+1i+1i+1 两台电脑都有开启的话，iii 号电脑也自动开启，这就说明题目限制了如果两个段的之间的长度 ≤1\le 1≤1 的话，就会自动合并成一段，这便启发了我们状态的设计：相邻两个段之间的长度为 ≥2\ge 2≥2 的未知数。

注意：这里的未知数指的是中间一定有超过一个电脑，相当于中间有 222 个电脑和中间有 333 个电脑的状态是等价的。

考虑这种方法会不会导致状态有重叠，答案是不会。

因为考虑最终的操作序列，肯定最后合并成了一段，合并成了一段就不存在某两段之间至少有 222 台电脑这个说法了，并且因为中间有 222 个电脑和中间有 333 个电脑的状态是等价的，故考虑转移的时候也不会重复。

既然都推到这里了，那么 DP 方程就出来了。

首先，单独形成一段，dpi,j=j×dpi−1,j−1dp_{i,j}=j \times dp_{i-1,j-1}dpi,j​=j×dpi−1,j−1​。

然后加在某段的两边（这里的左右边是一样的，故不分开讨论）：dpi,j=j×2×dpi−1,jdp_{i,j} = j \times 2 \times dp_{i-1,j}dpi,j​=j×2×dpi−1,j​。

最后连接连段，如果两段中间的未知数等于 222，那可以开 222 台中的任意一台；如果未知数等于 333，那只能开中间那台；如果未知数是 444 或更多，开的电脑就不止一台，并且都是上述 222 种情况的延伸。dpi,j=j×dpi−3,j+1+j×2×dpi−2,j+1dp_{i,j}=j \times dp_{i-3,j+1}+j \times 2 \times dp_{i-2,j+1}dpi,j​=j×dpi−3,j+1​+j×2×dpi−2,j+1​。注意这里 iii 为什么要 −2-2−2 或者 −3-3−3，因为它会自动开启 2,32,32,3 台电脑。

最后注意一下，这次枚举的顺序就是开机的顺序了，并不是电脑编号的顺序，因为题目的自动与手动是按照开机的顺序以及位置决定的，与电脑编号没有关系。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,mod,i,j,dp[405][405];
int main(){
	cin>>n>>mod;
	dp[0][0] = 1;
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			dp[i+1][j+1] = (dp[i+1][j+1]+dp[i][j]*(j+1))%mod;
			dp[i+1][j] = (dp[i+1][j]+dp[i][j]*2*j)%mod;
			dp[i+2][j] = (dp[i+2][j]+dp[i][j]*2*j)%mod;
			if(j>=2){
				dp[i+2][j-1] = (dp[i+2][j-1]+dp[i][j]*(j-1)*2)%mod;
				dp[i+3][j-1] = (dp[i+3][j-1]+dp[i][j]*(j-1))%mod;
			}
		}
	}
	cout<<dp[n][1]<<endl;
}

总结

总结其实都写在例题和习题讲评里面了，复制粘贴一遍其实没有用，重要的是去理解，并且收获自己的感受，这样才能让做题的思路更加敏捷精确。这就是插入 DP，一个非常巧妙但是很难理解的 DP 类型。

作者：Acoipp    创建时间：111 不推荐
  • 插入类型 DP 学习笔记
  • 插入类型 DP
  • 形式
  • 引入
  • 实践
  • 确定元素添加顺序
  • 确定状态转移
  • 小结
  • 习题
  • 部分习题讲评
  • CF704B-Ant Man
  • [JOI Open 2016] 摩天大楼
  • [ABC209F] Deforestation
  • CF1515E-Phoenix and Computers
  • 总结

标签：ai,dpi,笔记,插入,DP,1i,iii,dp
From： https://www.cnblogs.com/gutongxing/p/18389013

相关文章

  • C#学习笔记本--第三篇（排序算法之归并排序）
    一、基本原理：//归并=递归+合并//数组分左右 //左右元素相比较//满足条件放入新数组//一侧用完放对面//递归不停分分完在排序//排序结束往上走边走边合并//走到头顶出结果//归并排序分为两部分//1.基本排序规则//2.递归平分数组//递归平分数组：//不停地分割......
  • CMake构建学习笔记11-minizip库的构建
    准确来说，minizip其实是zlib提供的辅助工具，位于zlib库的contrib文件夹内。minizip提供了更为高级一点的接口，能直接操作文件进行压缩。不过，有点麻烦的是这个工具并没有提供CMake构建的方式。那么可以按照构建giflib的方式，自己组织CMakeList.txt，正好这个项目的代码量并不多。另一个......
  • MySQL-进阶篇-SQL优化（插入数据优化、主键优化、order by优化、group by优化、limit优
    文章目录1.插入数据优化1.1使用批量插入1.2批量插入数据时手动提交事务1.3按主键的顺序插入1.4大批量插入数据时使用load指令2.主键优化2.1数据组织方式2.2页分裂2.3页合并2.4主键的设计原则2.4.1降低主键的长度2.4.2使用AUTO_INCREMENT自增主键2.4.3......
  • nginx编译参数和配置参数笔记
    编译参数： ./configure --prefix=/etc/nginx--sbin-path=/usr/sbin/nginx--modules-path=/usr/lib64/nginx/modules--conf-path=/etc/nginx/nginx.conf--error-log-path=/var/log/nginx/error.log--http-log-path=/var/log/nginx/access.log--pid-path=/var/run/nginx.pi......
  • FFmpeg开发笔记（四十八）从0开始搭建直播系统的开源软件架构
    音视频技术的一个主要用途是直播，包括电视直播、电脑直播、手机直播等等，甚至在线课堂、在线问诊、安防监控等应用都属于直播系统的范畴。由于直播系统不仅涉及到音视频数据的编解码，还涉及到音视频数据的实时传输，因此直播领域采用的网络技术标准比较高，实现起来也比一般的WEB系统复杂......
  • 结构开发笔记（六）：solidworks软件(五)：绘制M2x3.0mm螺丝
    若该文为原创文章，转载请注明原文出处本文章博客地址：https://hpzwl.blog.csdn.net/article/details/141499374长沙红胖子Qt（长沙创微智科）博文大全：开发技术集合（包含Qt实用技术、树莓派、三维、OpenCV、OpenGL、ffmpeg、OSG、单片机、软硬结合等等）持续更新中…硬件相关开发......
  • 学习笔记4——二叉树（C++版）
    关于二叉树的算法题一般都是使用递归来实现，所以要想做好二叉树的算法题，要先学会递归算法的使用。一、如何创建一个二叉树1.声明一个树节点结构体structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),ri......
  • 在中国使用wordpress建网站的主要有三类人
    在中国，使用WordPress建网站的主要有三类人：做IT技术程序员、海归人士和做外贸的老板。这三类人选择WordPress的原因可以从WordPress的多个优势中找到答案。做IT技术程序员选择WordPress的原因在于其高度的可扩展性和灵活性。WordPress的模块化设计和强大的插件生态系统使得程序......
  • Min_25 筛学习笔记
    \(\text{Min}\_25\)筛学习笔记事实上我又学习了一个有点春的筛法。\(\text{Min}\_25\)筛用于求解积性函数的前缀和，即形如\(g(n)=\sum_{i=1}^{n}f(i)\)形式的函数\(g\)。众所周知，朴素筛法之所以无法做到低于线性是因为枚举了区间内的每一个数，那么我们想要做到低于线性，就必然......
  • 树形dp的各种应用题型与模板
    ///**//低落...最近做了以及看了树形dp这部分的知识，感觉有必要做一些整理，所以特来此地写下来。我将整理一些树形dp基本的模板与应用以及思想。1.树的直径：树上最长的链概念应该很好懂，那么现在来看看代码（简略版）：#include<iostream>usingnamespacestd;structEDGE{ int......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99