区间dp及经典例题

区间dp:

区间dp就是在区间上进行动态规划,求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。

主要思路:既然让我求解在一个区间上的最优解,那么我把这个区间分割成一个个小区间,求解每个小区间的最优解,再合并小区间得到大区间即可。

例题1:括号匹配

We give the following inductive definition of a “regular brackets” sequence:

the empty sequence is a regular brackets sequence,
if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
if a and b are regular brackets sequences, then ab is a regular brackets sequence.
no other sequence is a regular brackets sequence
For instance, all of the following character sequences are regular brackets sequences:

(), [], (()), ()[], ()[()]

while the following character sequences are not:

(, ], )(, ([)], ([(]

Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence.

Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

Input
The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

Output
For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

Sample Input

1
2
3
4
5
6
((()))
()()()
([]])
)[)(
([][][)
end

Sample Output

1
2
3
4
5
6
6
4
0
6

用二维数组f[i][j]表示从i~j的最大匹配数,还有个比较重要的思想是拆分思想,就是把f[i][j],拆分为f[i][k]+f[k+1][j]两部分的和,在取最大,就是dp的选择过程。
AC代码:

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
#include<iostream>
#include<cstring>
using namespace std;
int f[110][110];
int main()
{
string a;
while(cin>>a&&a!="end")
{
memset(f,0,sizeof(0));//初始化
int n=a.length();
for(int d=2;d<=n;d++)//间隔长度,括号总是成对出现,所以间隔取2.
{
for(int i=0;i<n;i++)
{
int j=i+d-1;//每一段的右结点
if(j>n) break;
if((a[i]=='('&&a[j]==')')||(a[i]=='['&&a[j]==']'))//匹配
f[i][j]=f[i+1][j-1]+2;//+2是因为括号是一对
else
f[i][j]=f[i+1][j-1];//不匹配则不变
for(int k=i;k<j;k++)
{
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);//核心,拆分过程
}
}
}
cout<<f[0][n-1]<<"\n";
}
}

例题2:(经典)石子合并问题–直线版

一条直线上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆石子数记为该次合并的得分。请编辑计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。
Input
输入有多组测试数据。

每组第一行为n(n<=100),表示有n堆石子,。

二行为n个用空格隔开的整数,依次表示这n堆石子的石子数量ai(0<ai<=100)

Output
每组测试数据输出有一行。输出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。 中间用空格分开。

Sample Input

1
2
3
3

1 2 3

Sample Output

1
9 11

这个题是区间dp的经典问题,很容易联想到贪心算法里面的合并果子,但那个是任意两堆可以合并,但是这个题中只能是相邻的合并,嗯,That’s good~。
和上个题一样,我们需要设置maxx[i][j]和minn[i][j]分别来储存从i~j堆的合并最小消耗值。并用sum[i]记录一下前缀和。
复杂度O(n^3^)
AC代码:

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
#include<bits/stdc++.h>
using namespace std;
int maxx[110][110];
int minn[110][110];
int sum[110];
int main()
{
int n;
while(cin>>n)
{
sum[0]=0;
memset(maxx,0,sizeof(maxx));
memset(minn,0,sizeof(minn));
for(int i=1;i<=n;i++)
{
cin>>sum[i];
sum[i]+=sum[i-1];
}
for(int d=1;d<=n;d++)
{
for(int i=1;i+d<=n;i++)
{
int j=i+d;
minn[i][j]=99999999;//除了min[i][i]都赋值最大,因为自己合并自己消耗值是0.
for(int k=i;k<j;k++)
{
maxx[i][j]=max(maxx[i][j],maxx[i][k]+maxx[k+1][j]+sum[j]-sum[i-1]);
minn[i][j]=min(minn[i][j],minn[i][k]+minn[k+1][j]+sum[j]-sum[i-1]);
}
}
}
cout<<minn[1][n]<<' '<<maxx[1][n]<<'\n';

}
}

但是复杂度非常高,如果n<=1000就无法通过了,所以我们需要考虑用四边形不等式优化,接近O(n^2^).
(暂时还不会,会了再贴上)

例题3:(升级)石子合并问题–圆形版

在圆形操场上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆石子数记为该次合并的得分。请编辑计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。
Input
输入有多组测试数据。
每组第一行为n(n<=100),表示有n堆石子,。

二行为n个用空格隔开的整数,依次表示这n堆石子的石子数量ai(0<ai<=100)

Output
每组测试数据输出有一行。输出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。 中间用空格分开。
Sample Input

1
2
3
1 2 3

Sample Output

1
9 11

与上个题大体相同,不同的地方在于这些石子是首位相接的环状,也就是说第一个与最后一个也能够进行合并。
所以就比较好想了,我们可以设置二倍大小的数组,中间的dp过程相同,唯一不同的就是dp结束后,需要寻找开始和结束点,来使消耗值最小。
AC代码:

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
#include<bits/stdc++.h>
using namespace std;
int maxx[220][220];
int minn[220][220];
int sum[220];
int a[110];
int main()
{
int n;
while(cin>>n)
{
sum[0]=0;
memset(maxx,0,sizeof(maxx));
memset(minn,0,sizeof(minn));
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int i=n+1;i<=2*n;i++)//2*n!
sum[i]=sum[i-1]+a[i-n];
for(int d=1;d<=n*2;d++)
{
for(int i=1;i+d<=n*2;i++)
{
int j=i+d;
minn[i][j]=99999999;//除了min[i][i]都赋值最大,因为自己合并自己消耗值是0.
for(int k=i;k<j;k++)
{
maxx[i][j]=max(maxx[i][j],maxx[i][k]+maxx[k+1][j]+sum[j]-sum[i-1]);
minn[i][j]=min(minn[i][j],minn[i][k]+minn[k+1][j]+sum[j]-sum[i-1]);
}
}
}
int ansmin=99999999;
int ansmax=0;
for(int i=1;i<=n;i++)
{
ansmin=min(ansmin,minn[i][i+n-1]);
ansmax=max(ansmax,maxx[i][i+n-1]);
}
cout<<ansmin<<' '<<ansmax<<'\n';

}
}

坚持原创技术分享,您的支持也将成为我的动力!
-------------本文结束感谢您的阅读-------------
undefined