区间DP的一些理解

区间$\text{DP}$比线性$\text{DP}$好想一些。

合并沙子

对于一道典型的区间$\text{DP}$问题,我们很容易思考到如何划分区间(集合)?

显然,最小的区间是每个数本身,此时合并花费一定最少(因为不需要花费)

考虑两个数作为一个区间,此时无论怎么合并花费一定最少(只有一种合并方法)

对于三个数及以上显然不存在直接合并一定最少的情况,例如 $1,3,100$ 如果先合并 $3,100$ 再合并 $1,103$ 总花费是 $207$ ,先合并 $1,3$ 再合并 $4,100$ 总花费则为 $108$。

那我们可以一直划分一个长度大于等于三的区间,那么显然前一部分的最小加上后一部分的最小使得总体最小,满足最优子结构

其中 $f(i,j)$ 表示合并 $i\sim j$ 的最小花费 $cost(i,j)$ 为合并 $i,j$ 的最小代价

想知道 $cost(i,j)$ 可以采用前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
//f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+sum(l,r)(l<=k<=r)
int n,a[305],b[305],f[305][305];
int main() {
memset(f,0x3f,sizeof(f));
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
b[i]=b[i-1]+a[i],f[i][i]=0;
}
for(int len=1;len<n;len++)
for(int l=1;l+len<=n;l++) {
int r=len+l;
for(int k=1;k<r;k++)
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+b[r]-b[l-1]);
}
printf("%d",f[1][n]);
return 0;
}

枚举每一个长度 $\text{len}$ 的序列的最小合并花费,最终求出 $f(1,n)$ 即最终的最小花费。

环形合并石子

有了上一题的经验,很容易知道这一题的结论也是 $f(i,j) = \min \{ f(i,k) + f(k+1,r) \} + sum(i,j)$

难点在于环形,我们可以用一个简单的办法解决,原序列展开最多 $n$ 的长度,我们只需要把整个序列复制一遍使其能够计算到 $2n$ 的位置就可以了

a[i+n]=a[i];

对于最大值和最小值可以开两个数组 f, g 来解决,本质是一样的,但是要枚举每次长度为 $n$ 的序列的起始点才能找到最大值和最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
//f[i][j]=min(f[l][r],f[i][k]+f[k+1][r])+sum(l,r)(l<=k<=r)
int n,a[605],b[605],f[605][605],g[605][605],res1=0x7fffff,res2;
int main() {
memset(f,0x3f,sizeof(f));
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
a[i+n]=a[i];
}
for(int i=1;i<=n*2;i++) b[i]=b[i-1]+a[i],f[i][i]=g[i][i]=0;
for(int len=1;len<n;len++) {
for(int l=1;l+len<=n*2;l++) {
int r=l+len;
for(int k=l;k<r;k++)
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+b[r]-b[l-1]);
g[l][r]=max(g[l][r],g[l][k]+g[k+1][r]+b[r]-b[l-1]);
}
}
for(int i=1;i<=n;i++) res1=min(res1,f[i][i+n-1]),res2=max(res2,g[i][i+n-1]);
printf("%d\n%d",res1,res2);
return 0;
}

加分二叉树

为什么树也是区间$\text{DP}$?

这里运用了中序遍历的性质(拍扁序)直接成为了一个区间

每次如果能够更新则根的序号改变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
//f[i][j]=max(f[i][k-1]*f[k+1][j]+a[k])(l<=k<=r)
//k==l||k==r 特殊处理
int n,a[35],f[35][35],g[35][35];
void dfs(int l,int r) {
if(l>r)
return;
printf("%d ",g[l][r]);
dfs(l,g[l][r]-1);
dfs(g[l][r]+1,r);
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
f[i][i]=a[i];
//叶子节点就直接是自己
g[i][i]=i;
}
for(int len=1;len<n;len++) {
for(int l=1;l+len<=n;l++) {
int r=l+len;
for(int k=l;k<=r;k++) {
if(k==l) {
if(f[l][r]<a[l]+f[k+1][r])
f[l][r]=a[l]+f[k+1][r],g[l][r]=k;
//f[l][r]=max(f[l][r],a[l]+f[k+1][r]);
}
else if(k==r) {
if(f[l][r]<a[r]+f[l][k-1])
f[l][r]=a[r]+f[l][k-1],g[l][r]=k;
//f[l][r]=max(f[l][r],a[r]+f[l][k-1]);
}
else {
if(f[l][r]<a[k]+f[l][k-1]*f[k+1][r])
f[l][r]=a[k]+f[l][k-1]*f[k+1][r],g[l][r]=k;
//f[l][r]=max(f[l][r],a[k]+f[l][k-1]*f[k+1][r]);
}
}
}
}
printf("%d\n",f[1][n]);
dfs(1,n);
return 0;
}

限于作者本人能力有限,期待各位多提些建议

文章作者: answerend42
文章链接: http://answerend42.github.io/2020/04/17/%E5%8C%BA%E9%97%B4DP%E7%9A%84%E4%B8%80%E4%BA%9B%E7%90%86%E8%A7%A3/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 answerend42的Blog