“随着方程推进，登峰造极。”
定义
在区间上进行动态规划，从而求解一段区间上的最优解。通过合并小区间递推出大区间的 $dp$ 算法。
思路/实现
合并：即将两个或多个部分进行整合，当然也可以反过来；
特征：能将问题分解为能两两合并的形式；
求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。
一般来说，其转移方程都与：
$dp_{i,j}=\max\{dp_{i,j},dp_{i,k}+dp_{k,j}+cost_k\},k \in [l,r]$
类似。注意，此处的 $\max$ 并不一定指数值上的较大值。
一般来说，能够达到 $O(n^3)$ 复杂度的题都要考虑区间 $dp$ 。对于小部分题而言，能够用四边形不等式优化到 $O(n^2)$ 。
区间dp的三种写法
都可以证明出是从小区间到大区间。
$len$ 表示区间长度，$l$ 表示左端点， $r$ 表示右端点。$k$ 为枚举点。
1
2
3
4
5
6
7
| for(int len=1;len<=n;++len)
for(int l=1;l<=n-len+1;++l)
{
int r=l+len-1;
for(int k=l;k<=r;++k)
}
|
1
2
3
4
| for(int l=n;l>=1;--l)
for(int r=l;r<=n;++r)
for(int k=l;k<=r;++k)
|
1
2
3
4
| for(int r=1;r<=n;++r)
for(int l=r;l>=1;--l)
for(int k=l;k<=r;++k)
|
没什么太大区别，看自己习惯。
例题
题意
给定 $n$ 个数，每次操作将相邻两堆合并。得分为两个数字的和。求最大得分和最小的分。
思路
暴力：
暴力合并，时间复杂度 $O(n!)$
区间dp：
对于每一个状态 $dp_{i,j}$ 都可由 $dp_{i,k}$ 与 $dp_{k+1,j}$ 转移而来。
$dp_{i,j}=\max\{dp_{i,j},dp_{i,k}+dp_{k+1,j}\},k \in [i,j]$
具体过程还需读者自行思考。
AC Code
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
using namespace std;
using std::cin;
using std::cout;
int n,Stone[201];
int StonePrime[201];
int F[201][201],MaxG;
int G[201][201],MinF=1e9;
inline int Min(int a,int b)
{
return a>b?b:a;
}
inline int Max(int a,int b)
{
return a>b?a:b;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
F[i][i]=0;
G[i][i]=0;
}
StonePrime[0]=0;
for(int i=1;i<=n;++i)
{
scanf("%d",&Stone[i]);
Stone[i+n]=Stone[i];
}
for(int i=1;i<=2*n;++i)
{
StonePrime[i]=Stone[i]+StonePrime[i-1];
}
for(int p=1;p<n;++p)
{
for(int i=1,j=p+i;(i<n*2)&&(j<2*n);++i,j=p+i)
{
F[i][j]=1e9;
for(int k=i;k<j;++k)
{
F[i][j]=Min(F[i][j],F[i][k]+F[k+1][j]+StonePrime[j]-StonePrime[i-1]);
G[i][j]=Max(G[i][j],G[i][k]+G[k+1][j]+StonePrime[j]-StonePrime[i-1]);
}
}
}
for(int i=1;i<=n;++i)
{
MinF=Min(MinF,F[i][i+n-1]);
MaxG=Max(MaxG,G[i][i+n-1]);
}
printf("%d\n%d",MinF,MaxG);
return 0;
}
|
转移方程
$dp_{l,r}=\max\{dp_{l,r},dp{l,k}+dp{k,r}+val_l\times val_k\times val_r\},k \in [l,r]$
AC Code
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
47
48
49
50
51
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
using namespace std;
using std::cin;
using std::cout;
int n,Power[201];
int G[201][201],MaxG;
inline int Min(int a,int b)
{
return a>b?b:a;
}
inline int Max(int a,int b)
{
return a>b?a:b;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&Power[i]);
Power[i+n]=Power[i];
}
for(int i=2;i<n*2;++i)
{
for(int j=i-1;i-j<n&&j>=1;--j)
{
for(int k=j;k<i;++k)
{
G[j][i]=Max(G[j][i],G[k+1][i]+G[j][k]+Power[j]*Power[k+1]*Power[i+1]);
}
MaxG=Max(MaxG,G[j][i]);
}
}
printf("%d",MaxG);
return 0;
}
|
其他题目
DCOJ#.2008蜜雪冰城
P7914 [CSP-S 2021] 括号序列