区间dp

前情提要

先赞后看，必成习惯

一、区间dp-常见的也常考的dp

1.区间dp是什么？

区间动态规划是用 dp的状态来表示和一段区间有关的性质，比如说dp[i] [j]表示解决区间 [i,j] 上的子问题的最小代价或最大收益，然后利用区间子问题之间的关系递推求解。

2.区间dp怎么写？

区间dp常见的有两种写法，一种是两层for循环递推直接写，另外一种则是利用记忆化搜索递归求解

那么两种打法都来试一下下

第一种：

 for(int len=2;len<=n;len++){
    	for(int l=1;l+len-1<=2*n;l++){
    		int r=l+len-1;
    		dp[l][r][1]=inf;
    		dp[l][r][0]=-inf;
    		//这里写你的dp方程式，例如
    		for(int t=l;t+1<=r;t++){//这里是用来枚举断点，即，他可以从两个不交的自己转移过来，于是就n*n*n了
    			dp[l][r][0]=max(dp[l][r][0],dp[l][t][0]+dp[t+1][r][0]+pre[r]-pre[l-1]);
    			dp[l][r][1]=min(dp[l][r][1],dp[l][t][1]+dp[t+1][r][1]+pre[r]-pre[l-1]);
    		}
    	}
    }

注意要点：

第一层循环枚举的长度，第二层则是起始点

第二种：

int dfs(int i,int j){
	if(j-i<=1){
        return dp[i][j]=0;
	}
	if(dp[i][j] != INF){
       return dp[i][j];
	}
	long long sum = a[i]*a[j];
	for(int k=i+1;k<j;k++){
		dp[i][j] = min(dp[i][j],dfs(i,k)+dfs(k,j)+sum*a[k]);
	}
	return dp[i][j];
}

注意要点：

第一是边界，注意下如果超过边界了应当return什么

第二是记忆化搜索，不然超时GG

第三就是给初始值，这边建议可以在dfs中给初始值,例如：if(x==y),dp[x] [y]=…; return …

区间dp什么时候写？

当你发现，诶,起始点好像并不一定是1时，同时发现区间不会有间断，同时发现一段区间有统一性

什么叫间断？就是说，不会1到k有值, k+1到m没值， 然后m+1到n又有值了

什么叫有统一性？就是说我要找的这段区间可以有表达同一个量的能力（但其实一般dp也是有的）

同时，优化时间复杂度也可以往这边靠一靠哦

二、有关区间dp的模型

1.字符串对应序列

字符串大家肯定是有所理解的，什么叫对应序列呢?就是说你可以让他加加减减满足题目条件，最后要求满足题目条件的最小的操作花费

一道例题

字串S长M，由N个小写字母构成。欲通过增删字母将其变为回文串，增删特定字母花费不同，求最小花费。

第一行：两个由空格分隔的整数：n 和 m。

第二行：这一行正好包含构成初始标签的 m 个字符。

第三行到 n+2 行：每行包含三个空格分隔的整数：一个字符和两个整数，分别是添加该字符和删除该字符的成本。

详细讲解见下面重要的部分代码

long long dfs(int x,int y){//x到y的最小花费
    if(dp[x][y]!=-1){
		return dp[x][y];
	}//记忆化搜索
	if(x>y){
		dp[x][y]=0;
		return 0;
	}
	if(x==y){
		dp[x][y]=0;
		return 0;
	}//以上两个if是为了“初始化”和“边界处理”
	if(s[x]==s[y]){
        dp[x][y]=dfs(x+1,y-1);
        return dp[x][y];
	}//这就是“匹配”，这两段要是符合要求的话就不用修改
	long long ans=INT_MAX;
	ans=min(dfs(x,y-1)+min(add[s[y]],del[s[y]]),dfs(x+1,y)+min(add[s[x]],del[s[x]]));
    //不匹配的情况下，可以从那些地方转移过来，注意一定要枚举完
    dp[x][y]=ans;//记忆化
    return dp[x][y];

}

更难的题

[P7914 CSP-S 2021] 括号序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这个呢，涉及到各种判断重复，以及多部分转移

很难，非常难，特别难，问题就在于，怎么拆分可以让他不重不漏

拆分是什么意思呢，就是将“文法”拆成各种不同的新“文法”，并且这些新的“文法”互不干扰“

“文法”又是什么呢？就是题目给你的字符串的变化规则，例如s->(s);s->()等等，这个要找全也很难

说实话，我不看题解真的不会

2.关灯模型

关灯模型的特点在于，你会在特定的一段路程上（或者可以说成排成一条线的点上）来回移动，并维护某一个最值

相比于上一个区间dp，他会多一维[0/1],表示现在这个人干完了x到y的所有事件后，现在站在这一段路的x点（0）/y点（1）

当然，这个dp也会有一个好处，那就是他的转移情况0/1每种有且只有两种来源，不需要想太多

if(op) dp[x][y][op]=min(dfs(x,y-1,0)+mp[dot[y].id][dot[x].id],dfs(x,y-1,1)+mp[dot[y].id][dot[y-1].id]);
else dp[x][y][op]=min(dfs(x+1,y,0)+mp[dot[x+1].id][dot[x].id],dfs(x+1,y,1)+mp[dot[y].id][dot[x].id]);

mp看不懂什么意思，他的意思就是mp[x] [y]表示x和y之间的权值

好像很难看？还是不太懂？

那么就这样吧：

if(op) dp[x][y][op]=min(dfs(x,y-1,0)+权值a,dfs(x,y-1,1)+权值b);
else dp[x][y][op]=min(dfs(x+1,y,0)+权值c,dfs(x+1,y,1)+权值d);

要注意哦，权值可能是不一样的，因此要一步一步慢慢来

一道特特特特特特典型的题目

[P1220 关路灯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

(https://www.luogu.com.cn/problem/P1220)

不多bb，上代码注释讲解

#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;int n,c;
int len,dp[55][55][2];
int w[55],pre[55];
long long dfs(int x,int y,bool op){
	if(x>y){
		dp[x][y][op]=INT_MAX-5;
		return INT_MAX-5;
	}
	if(dp[x][y][op]!=-1){
		return dp[x][y][op];
	}//处理边界以及记忆化搜索，这一次我把初始化放在下面的，一定要去看一下
	dp[x][y][op]=INT_MAX-1;//不是上面两种情况的话，我是找最小值，所以这里给的int_max
	dp[x][y][0]=min(dfs(x+1,y,0)+(w[x+1]-w[x])*(pre[x]+pre[n]-pre[y]),dfs(x+1,y,1)+(w[y]-w[x])*	(pre[x]+pre[n]-pre[y]));//其实dfs是一样的，w[]-w[]目的是找到这一段的距离（也就是时间），pre[x]+pre[n]-pre[y]就是这一段以外的其他灯的效率和（注意不包含下一步要关的灯在内）
	dp[x][y][1]=min(dfs(x,y-1,0)+(w[y]-w[x])*(pre[x-1]+pre[n]-pre[y-1]),dfs(x,y-1,1)+(w[y]-w[y-1])*(pre[x-1]+pre[n]-pre[y-1]));//同理
    //综上其实可以发现，01不同，转移的来源也就不同，从而导致了答案的多样性
	return dp[x][y][op];

}

signed main() {
    ios::sync_with_stdio(false);
    memset(dp,-1,sizeof(dp));
	cin >> n >> c;
	for(int i=1;i<=n;i++){
		int a;
		cin >> w[i] >> a;
		pre[i]=pre[i-1]+a;
	}
	dp[c][c][0]=0;
	dp[c][c][1]=0;//这里是初始化哦------------------------------------------

	cout<<min(dfs(1,n,0),dfs(1,n,1));
}

那我该什么时候用这个模型呢

看到“反复走一段区间”，同时区间不会中断，同时贪心不一定最优的情况下优先选择，同时最终在这一段区间左侧和在这一段区间右侧会导致答案不同的情况下可以尝试

粉饰后的题——是的你已经更上一层楼了

[P9119 春季测试 2023] 圣诞树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

如果你觉得你已经对前面的掌握的差不多了，可以看看这个：

至于题目还是在luogu里看吧，这个不知道为什么有点…

…难看？

[春季测试] 圣诞树错题重做 - 铃狐sama - 博客园 (cnblogs.com)

挂载模型

挂载模型说的是可以删去序列的一段区间，然后序列没被删去的部分会自动合并起来，形成一个新的连续的序列
例如下面这个题：
有一个序列，每次可以选择数值相同的连续的一段删除，若删除的一段长度为x，则获得x^2的分数，求最大得分
例如122233331，先消掉222和3333，得到25分，然后剩下的是11，再消掉，共得到29分

不能直接使用区间dp，因为你会发现，你不知道是合并前答案会最优还是合并后答案会最优

于是我们就有了挂载模型——加一点维数来表示这一段后面有没有什么可能改变当前答案的维度

不好说，上例题

一道例题

P2135 方块消除 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

对于这种题，我们dp方程式会有

所以设状态f[l] [r] [t]表示消去区间[l,r]，但是已经有t个和col[r]相同的块挂载在col[r]后面了。有两种转移：
第一种，把col[r]这种数值的数全部消去，一共有len[r]+t个
第二种，在[l,r-1]中找一个位置k，col[k]=col[r]，那么我们可以把[k+1,r-1]这一段消掉，col[r]这种数值的数的个数会继续增加，一共 有len[k]+len[r]+t个，或者说有len[r]+t个和col[k]相同的块挂载在col[k]后面
写成dp方程就是f[l] [r] [t]=max(f[l] [r-1] [0]+(len[r]+t)^2,f[l ] [k] [len[r]+t]+f[k+1] [r-1] [0]) （col[k]=col[r],l<=k<r）

代码：

#include<bits/stdc++.h>
using namespace std;
int dp[255][255][255];
int col[405];
int len[405];
int dfs(int l,int r,int left){
	int sum=len[r]+left;
	if(l==r){
        //dp[l][r][left]=sum;
        //dp[l][r][left]*=sum;本来就是0，后面记忆化会出问题
        return sum*sum;
	}
	if(dp[l][r][left]!=-1){
        return dp[l][r][left];
	}
	int ret=dfs(l,r-1,0)+sum*sum;//消除后面的
	for(int k=l;k<r;k++){//中间炸开
		if(col[k]==col[r]){
            ret=max(ret,dfs(k+1,r-1,0)+dfs(l,k,sum));
		}
	}
	dp[l][r][left]=ret;
	return ret;
}

int main(){
    ios::sync_with_stdio(false);
	int n;
	cin >> n;
	for(int i=1;i<=n;i++){
        cin >> col[i];
	}
	for(int i=1;i<=n;i++){
        cin >> len[i];
	}
	memset(dp,-1,sizeof(dp));
//	cout<<dp[1][4][0];
	cout<<dfs(1,n,0);
	
}

另一道题

[P5336 THUSC2016]成绩单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这一道题很明显也是有“合并”和后继性的，但根据题目要求，他想要min和max,那我就给他挂在min和max

转移还是差不多，不然炸裂，不然消掉

这里就是，不然中断，不然消掉

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[55][55][55][55];
int a[55],b[55];
int n;
int A,B;
int dfs(int l,int r,int mi,int mx){
	if(l>r){
        return 0;//这里错了
	}
	if(l==r){
            return A+B*(b[max(mx,a[l])]-b[min(mi,a[l])])*(b[max(mx,a[l])]-b[min(mi,a[l])]);
	}
	int ans=dp[l][r][mi][mx];
	if(ans<0x3f3f3f){
        dp[l][r][mi][mx]=ans;
        return ans;
	}
	for(int i=l;i<r;i++){//中间分开（炸掉）
        ans=min(ans,dfs(l,i,min(mi,a[r]),max(mx,a[r]))+dfs(i+1,r-1,n,1));
	}

	ans=min(ans,dfs(l,r-1,n,1)+A+B*(b[max(mx,a[r])]-b[min(mi,a[r])])*(b[max(mx,a[r])]-b[min(mi,a[r])]));
    //直接用掉
	dp[l][r][mi][mx]=ans;//这里忘记写了
	return ans;
}

signed main() {
    ios::sync_with_stdio(false);
	cin>>n>>A>>B;
	for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
	}
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+n+1,a[i])-b;//离散化
	}
	memset(dp,0x3f,sizeof(dp));
	cout<<dfs(1,n,n,1);
	return 0;
}

总结一下

这种挂载的特点是后继性和和并性，二转移大方向有两个：消掉后继和中间中断并生成新的后继