理论
区间
d
p
dp
d
p
是一种动态规划算法，用于解决区间问题。它的基本思想是将问题分解成若干子问题，然后通过递推求解整个问题。
下面是一个经典的区间
d
p
dp
d
p
问题：
给定一个长度为
n
n
n
的序列
a
a
a
，求
a
a
a
的一个子区间
[
l
,
r
]
[l,r]
[
l
,
r
]
，使得区间和最大。
我们可以定义一个状态
f
[
i
]
[
j
]
f[i][j]
f
[
i
]
[
j
]
表示区间
[
i
,
j
]
[i,j]
[
i
,
j
]
的最大和，然后通过状态转移方程来求解最优解。
状态转移方程为：
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
+
1
]
[
j
]
,
f
[
i
]
[
j
−
1
]
)
+
a
[
i
]
+
a
[
j
]
f[i][j] = max(f[i+1][j], f[i][j-1]) + a[i] + a[j]
f
[
i
]
[
j
]
=
ma
x
(
f
[
i
+
1
]
[
j
]
,
f
[
i
]
[
j
−
1
])
+
a
[
i
]
+
a
[
j
]
其中，
a
[
i
]
a[i]
a
[
i
]
表示序列a中第i个元素的值。这个方程的意义是，我们在区间
[
i
,
j
]
[i,j]
[
i
,
j
]
中选择一个端点，然后把这个端点前面或后面的区间作为子区间，使得区间和最大。
代码实现如下：
int n; // 序列的长度
int a[MAXN]; // 序列a
int f[MAXN][MAXN]; // 状态数组
int solve() {
for (int len = 2; len <= n; len++) { // 枚举区间长度
for (int i = 1; i + len - 1 <= n; i++) { // 枚举区间起点
int j = i + len - 1; // 区间终点
f[i][j] = max(f[i+1][j], f[i][j-1]) + a[i] + a[j];
}
}
return f[1][n]; // 返回整个序列的最大子区间和
}
在上面的代码中，我们先枚举区间长度
l
e
n
len
l
e
n
，然后再枚举区间起点
i
i
i
，计算出区间
[
i
,
j
]
[i,j]
[
i
,
j
]
的最大和。最终，我们返回整个序列的最大子区间和
f
[
1
]
[
n
]
f[1][n]
f
[
1
]
[
n
]
。
练习
关路灯
某一村庄在一条路线上安装了
n
n
n
盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。
为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。
现在已知老张走的速度为
1
m
/
s
1m/s
1
m
/
s
，每个路灯的位置（是一个整数，即距路线起点的距离，单位：
m
m
m
）、功率（
W
W
W
），老张关灯所用的时间很短而可以忽略不计。
请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。
输入格式
第一行是两个数字
n
n
n
（表示路灯的总数）和
c
c
c
（老张所处位置的路灯号）；
接下来
n
n
n
行，每行两个数据，表示第
1
1
1
盏到第
n
n
n
盏路灯的位置和功率。数据保证路灯位置单调递增。
输出格式
一个数据，即最少的功耗（单位：
J
J
J
，
1
J
=
1
W
×
s
1J=1W\times s
1
J
=
1
W
×
s
）。
样例输入 #1
5 3
2 10
3 20
5 20
6 30
8 10
样例输出 #1
270
提示
样例解释
此时关灯顺序为
3 4 2 1 5
。
数据范围
1
≤
n
≤
50
1\le n\le50
1
≤
n
≤
50
，
1
≤
c
≤
n
1\le c\le n
1
≤
c
≤
n
。
思路
- 比较典型的区间dp问题
-
观察发现关灯的顺序是从中心向两边扩展的区间，设
[0
/
1
]
[0/1]
[
0/1
]
表示把
[i
,
j
]
[i,j]
[
i
,
j
]
区间内灯关掉，结束时人在最左/最右时的最少耗电，有转移方程：
f[
i
]
[
j
]
[
0
]
=
m
i
n
(
f
[
i
+
1
]
[
j
]
[
0
]
+
d
(
i
,
i
+
1
)
∗
P
,
f
[
i
+
1
]
[
j
]
[
1
]
+
d
(
i
,
j
)
∗
P
)
f[i][j][0]=min(f[i+1][j][0]+d(i,i+1)*P,f[i+1][j][1]+d(i,j)*P)
f
[
i
]
[
j
]
[
0
]
=
min
(
f
[
i
+
1
]
[
j
]
[
0
]
+
d
(
i
,
i
+
1
)
∗
P
,
f
[
i
+
1
]
[
j
]
[
1
]
+
d
(
i
,
j
)
∗
P
)
f[
i
]
[
j
]
[
1
]
=
m
i
n
(
f
[
i
]
[
j
−
1
]
[
0
]
+
d
(
i
,
j
)
∗
P
,
f
[
i
]
[
j
−
1
]
[
1
]
+
d
(
j
−
1
,
j
)
∗
P
)
f[i][j][1]=min(f[i][j-1][0]+d(i,j)*P,f[i][j-1][1]+d(j-1,j)*P)
f
[
i
]
[
j
]
[
1
]
=
min
(
f
[
i
]
[
j
−
1
]
[
0
]
+
d
(
i
,
j
)
∗
P
,
f
[
i
]
[
j
−
1
]
[
1
]
+
d
(
j
−
1
,
j
)
∗
P
)
-
dd
d
为距离，
PP
P
可以用前缀和
第一个式子，因为i+1在数轴上在i的右边，所以是i是由i+1转移而来
题解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 55;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
ll f[N][N][2];
int P[N], L[N], n, c, pre[N];
int main(){
scanf("%d%d", &n, &c);
for(int i = 1; i <= n; ++i){
scanf("%d%d", L+i, P+i);
pre[i] = pre[i-1] + P[i];
}
for(int l = 1; l <= n; ++l){
for(int i = 1, j; (j = i + l - 1) <= n; ++i){
if(i <= c && c <= j){
f[i][j][0] =
min(
f[i+1][j][0] + (L[i+1] - L[i]) * (pre[n] - pre[j] + pre[i]),
f[i+1][j][1] + (L[j] - L[i]) * (pre[n] - pre[j] + pre[i])
);
f[i][j][1] =min(f[i][j-1][0] + (L[j] - L[i]) * (pre[n] - pre[j-1] + pre[i-1]), f[i][j-1][1] + (L[j] - L[j-1]) * (pre[n] - pre[j-1] + pre[i-1]));
}else f[i][j][0] = f[i][j][1] = INF;
}
}
printf("%lld\n", min(f[1][n][0], f[1][n][1]));
}
[CQOI2007]涂色
假设你有一条长度为
5
5
5
的木板，初始时没有涂过任何颜色。你希望把它的
5
5
5
个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为
5
5
5
的字符串表示这个目标：
RGBGR
\texttt{RGBGR}
RGBGR
。
每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木板涂成
RRRRR
\texttt{RRRRR}
RRRRR
，第二次涂成
RGGGR
\texttt{RGGGR}
RGGGR
，第三次涂成
RGBGR
\texttt{RGBGR}
RGBGR
，达到目标。
用尽量少的涂色次数达到目标。
输入格式
输入仅一行，包含一个长度为
n
n
n
的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。
输出格式
仅一行，包含一个数，即最少的涂色次数。
样例输入 #1
AAAAA
样例输出 #1
1
样例输入 #2
RGBGR
样例输出 #2
3
提示
40
%
40\%
40%
的数据满足
1
≤
n
≤
10
1\le n\le 10
1
≤
n
≤
10
。
100
%
100\%
100%
的数据满足
1
≤
n
≤
50
1\le n\le 50
1
≤
n
≤
50
。
思路
-
状态：
f[
i
]
[
j
]
f[i][j]
f
[
i
]
[
j
]
表示区间
[i
,
j
]
[i,j]
[
i
,
j
]
的最少操作次数 -
状态转移方程：
-
如果区间左右端点目标颜色相同，则可以免费涂最左或最右的一块：
f[
i
]
[
j
]
=
m
i
n
(
f
[
i
+
1
]
[
j
]
,
f
[
i
]
[
j
+
1
]
)
f[i][j]=min(f[i+1][j],f[i][j+1])
f
[
i
]
[
j
]
=
min
(
f
[
i
+
1
]
[
j
]
,
f
[
i
]
[
j
+
1
])
-
否则，从中间分成两个区间转移：
f[
i
]
[
j
]
=
m
i
n
(
f
[
i
]
[
k
]
,
f
[
k
+
1
]
[
j
]
)
f[i][j]=min(f[i][k],f[k+1][j])
f
[
i
]
[
j
]
=
min
(
f
[
i
]
[
k
]
,
f
[
k
+
1
]
[
j
])
-
如果区间左右端点目标颜色相同，则可以免费涂最左或最右的一块：
题解
#include<bits/stdc++.h>
using namespace std;
char s[55];
int f[55][55];
int main(){
scanf("%s",s);
int n=strlen(s);
memset(f,0x3f,sizeof(f));
for(int i=0;i<n;++i) f[i][i]=1;
for(int l=2;l<=n;++l){
for(int i=0,j;(j=i+l-1)<n;++i){
if(s[i]==s[j]) f[i][j]=min(f[i][j],min(f[i+1][j],f[i][j-1]));
else{
for(int k=i;k<j;++k)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
}
}
}
printf("%d",f[0][n-1]);
}
[HNOI2010]合唱队
为了在即将到来的晚会上有更好的演出效果，作为 AAA 合唱队负责人的小 A 需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共
n
n
n
个人，第
i
i
i
个人的身高为
h
i
h_i
h
i
米（
1000
≤
h
i
≤
2000
1000 \le h_i \le 2000
1000
≤
h
i
≤
2000
），并已知任何两个人的身高都不同。假定最终排出的队形是
A
A
A
个人站成一排，为了简化问题，小 A 想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终棑排出的队形中：
-
第一个人直接插入空的当前队形中。
-
对从第二个人开始的每个人，如果他比前面那个人高（
hh
h
较大），那么将他插入当前队形的最右边。如果他比前面那个人矮（
hh
h
较小），那么将他插入当前队形的最左边。
当
n
n
n
个人全部插入当前队形后便获得最终排出的队形。
例如，有
6
6
6
个人站成一个初始队形，身高依次为
1850
,
1900
,
1700
,
1650
,
1800
,
1750
1850, 1900, 1700, 1650, 1800, 1750
1850
,
1900
,
1700
,
1650
,
1800
,
1750
，
那么小 A 会按以下步骤获得最终排出的队形：
-
18501850
1850
。 -
1850,
1900
1850, 1900
1850
,
1900
，因为
1900>
1850
1900 > 1850
1900
>
1850
。 -
1700,
1850
,
1900
1700, 1850, 1900
1700
,
1850
,
1900
，因为
1700<
1900
1700 < 1900
1700
<
1900
。 -
1650,
1700
,
1850
,
1900
1650, 1700, 1850, 1900
1650
,
1700
,
1850
,
1900
，因为
1650<
1700
1650 < 1700
1650
<
1700
。 -
1650,
1700
,
1850
,
1900
,
1800
1650, 1700, 1850, 1900, 1800
1650
,
1700
,
1850
,
1900
,
1800
，因为
1800>
1650
1800 > 1650
1800
>
1650
。 -
1750,
1650
,
1700
,
1850
,
1900
,
1800
1750, 1650, 1700, 1850, 1900, 1800
1750
,
1650
,
1700
,
1850
,
1900
,
1800
，因为
1750<
1800
1750 < 1800
1750
<
1800
。
因此，最终排出的队形是
1750
,
1650
,
1700
,
1850
,
1900
,
1800
1750, 1650, 1700, 1850, 1900, 1800
1750
,
1650
,
1700
,
1850
,
1900
,
1800
。
小 A 心中有一个理想队形，他想知道多少种初始队形可以获得理想的队形。
请求出答案对
19650827
19650827
19650827
取模的值。
输入格式
第一行一个整数
n
n
n
。
第二行
n
n
n
个整数，表示小 A 心中的理想队形。
输出格式
输出一行一个整数，表示答案
m
o
d
19650827
\bmod 19650827
mod
19650827
的值。
样例输入 #1
4
1701 1702 1703 1704
样例输出 #1
8
提示
对于
30
%
30\%
30%
的数据，
n
≤
100
n \le 100
n
≤
100
。
对于
100
%
100\%
100%
的数据，
n
≤
1000
n \le 1000
n
≤
1000
，
1000
≤
h
i
≤
2000
1000 \le h_i \le 2000
1000
≤
h
i
≤
2000
。
思路
-
状态：
f[
i
]
[
j
]
[
0
/
1
]
f[i][j][0/1]
f
[
i
]
[
j
]
[
0/1
]
为目标队形中
[i
,
j
]
[i,j]
[
i
,
j
]
区间的方案数，且最后一个人在最左/右；状态转移：-
f[
i
]
[
j
]
[
0
]
f[i][j][0]
f
[
i
]
[
j
]
[
0
]
=
f[
i
+
1
]
[
j
]
[
0
]
∗
[
h
i
<
h
i
+
1
]
+
f
[
i
+
1
]
[
j
]
[
1
]
∗
[
h
i
<
h
j
]
f[i+1][j][0]*[h_i<h_{i+1}]+f[i+1][j][1]*[h_i<h_j]
f
[
i
+
1
]
[
j
]
[
0
]
∗
[
h
i
<
h
i
+
1
]
+
f
[
i
+
1
]
[
j
]
[
1
]
∗
[
h
i
<
h
j
]
-
f[
i
]
[
j
]
[
1
]
=
f
[
i
]
[
j
−
1
]
[
0
]
∗
[
h
j
>
h
i
]
+
f
[
i
+
1
]
[
j
]
[
1
]
∗
[
h
j
>
h
j
−
1
]
f[i][j][1]=f[i][j-1][0]*[h_j>h_i]+f[i+1][j][1]*[h_j>h_{j-1}]
f
[
i
]
[
j
]
[
1
]
=
f
[
i
]
[
j
−
1
]
[
0
]
∗
[
h
j
>
h
i
]
+
f
[
i
+
1
]
[
j
]
[
1
]
∗
[
h
j
>
h
j
−
1
]
-
题解
#include <bits/stdc++.h>
using namespace std;
int f[2010][2010][2],a[2010];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)f[i][i][0]=1;
for(int len=1;len<=n;len++)
for(int i=1,j=i+len;j<=n;i++,j++){
if(a[i]<a[i+1])f[i][j][0]+=f[i+1][j][0];
if(a[i]<a[j])f[i][j][0]+=f[i+1][j][1];
if(a[j]>a[i])f[i][j][1]+=f[i][j-1][0];
if(a[j]>a[j-1])f[i][j][1]+=f[i][j-1][1];
f[i][j][0]%=19650827;
f[i][j][1]%=19650827;
}
cout<<(f[1][n][0]+f[1][n][1])%19650827;
}
总结
当我们需要求解一个序列中某个子区间的最优解时，可以考虑使用区间dp算法。具体来说，我们需要思考以下几个问题：
- 状态设计：需要定义一个状态表示子区间的最优解。状态的设计通常与问题的性质密切相关，可以根据实际情况选择不同的状态表示方式。
- 状态转移方程：需要设计一个状态转移方程，根据已知状态推导出未知状态。状态转移方程通常是一个递推式，可以根据问题的性质和状态的定义来确定。
- 边界条件：需要确定最小的子问题的最优解，即边界条件。边界条件通常是一个或多个初始状态，可以根据实际情况选择不同的初始状态。
-
时间复杂度：需要考虑算法的时间复杂度，尽可能地优化算法实现，避免不必要的计算量和空间占用。
往往时间复杂度都在
O(
n
2
)
O(n^2)
O
(
n
2
)
，所以数据量如果过大则不宜适用这个算法
设计区间dp算法的关键在于状态设计和状态转移方程的确定。在实际操作中，可以先尝试暴力枚举所有子区间，然后根据已知的子区间最优解推导出更大的子区间最优解，最终得到整个序列的最优解。如果时间复杂度过高，则需要考虑优化算法实现，例如使用记忆化搜索等方法来避免重复计算。