区间DP小结

学习了区间DP,简单总结一下。

先拿一道例题说明,NOI1995石子合并不过话说23年前的NOI还真的是水啊。

简述题意。

在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。

试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

这道题乍一看上去可能会向贪心的方向想,用尽可能逼近目标的贪心法来解决问题。对于样例数据来说,贪心可以得到最优结果,但是并不是正解,好多选手使用了贪心策略丢了好多分。

考虑i和j堆石子合并的话,那么i和j之间的所有石子已经被合并,我们用区间[i,j]表示某一时刻某一堆石子,表示这堆石子是由最最开始状态的i~j堆石子合并而成的。

那么在这堆石子被合并出来前,必然是两堆石子,我们用区间[i,k]和[k+1,j]表示这两堆石子,区间[i,j]由[i,k]和[k+1,j]合并得到。

由此我们可以写出来转移方程

利用前缀和优化,可以得到

然后只要枚举区间长度就可以了。

就这样就可以了?当然不行。题目的要求是一个环,而我们的方程只是在链上的操作。

我可以枚举每一对起点和终点,进行n次dp得到结果。但是显然这个复杂度变成$O(n^2)$了。

我们先要将环处理为链,把长度为n的环变成长度为2n的链,就可以了。

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
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>

using std::cin;
using std::endl;
using std::cerr;
using std::cout;
using std::max;
using std::min;

typedef long long LL;

const int inf=0x7fffffff;
const LL linf=0x7fffffffffffffff;
const int maxn=210;

int n;
int a[maxn],sum[maxn];
int dp_max[maxn][maxn],dp_min[maxn][maxn];

int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[n+i]=a[i];
}

memset(dp_min,0x7f,sizeof dp_min);
for(int i=1;i<=2*n;i++)
{
sum[i]=sum[i-1]+a[i];
dp_min[i][i]=0;
}

for(int len=2;len<=n;len++)
{
for(int i=1,j;i<=n*2-len+1;i++)
{
j=i+len-1;
for(int k=i;k<j;k++)
{
dp_max[i][j]=max(dp_max[i][j],dp_max[i][k]+dp_max[k+1][j]);
dp_min[i][j]=min(dp_min[i][j],dp_min[i][k]+dp_min[k+1][j]);
}
dp_max[i][j]+=sum[j]-sum[i-1];
dp_min[i][j]+=sum[j]-sum[i-1];
}
}

int ans_max=0,ans_min=inf;
for(int i=1;i<=n;i++)
{
ans_max=max(ans_max,dp_max[i][i+n-1]);
ans_min=min(ans_min,dp_min[i][i+n-1]);
}
cout<<ans_min<<endl<<ans_max<<endl;
return 0;
}

NOIP2006能量项链

在Mars星球上,每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸盘是Mars人吸收能量的一种器官)的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m,尾标记为r,后一颗能量珠的头标记为r,尾标记为n,则聚合后释放的能量为m*r*n(Mars单位),新产生的珠子的头标记为 m,尾标记为n 。

需要时,Mars人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。

例如:设 N=4,4 颗珠子的头标记与尾标记依次为 (2,3),(3,5),(5,10),(10,2) 。我们用记号⊕表示两颗珠子的聚合操作,(j⊕k)表示第j,k两颗珠子聚合后所释放的能量。则第4 、11两颗珠子聚合后释放的能量为:

$(4⊕1) =10*2*3=60$。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为:

$((4⊕1)⊕2)⊕3)=10*2*3+10*3*5+10*5*10=710$。

用$head_i$表示第i颗珠子的头标记,$tail_i$表示第i颗珠子的尾标记。合并相邻两颗珠子释放的能量为

类似合并石子,用$dp_{i,j}$表示第i颗珠子到第j颗珠子之间都合并后产生的最大能量,那么,转移方程为:

本题同样需要处理环的问题。

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<cstdio>
#include<iostream>
#include<cstdlib>

using std::cin;
using std::endl;
using std::cerr;
using std::cout;
using std::max;

typedef long long LL;

const int inf=0x7fffffff;
const LL linf=0x7fffffffffffffff;
const int maxn=2010;

int n;
int head[maxn],tail[maxn];
int dp[maxn][maxn];

int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>head[i];
head[i+n]=head[i];
tail[i-1]=head[i];
tail[i+n-1]=head[i+n];
}
tail[n*2]=head[1];

for(int len=1;len<n;len++)
for(int i=1,j;i<n*2-len;i++)
{
j=i+len;
for(int k=i;k<j;k++)
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+head[i]*tail[k]*tail[j]);
}
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,dp[i][i+n-1]);
cout<<ans<<endl;
return 0;
}

NOIP2007矩阵取数游戏

帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n×m的矩阵,矩阵中的每个元素$a_{i,j}$均为非负整数。游戏规则如下:

  1. 每次取数时须从每行各取走一个元素,共n个。经过m次后取完矩阵内所有元素;
  2. 每次取走的各个元素只能是该元素所在行的行首或行尾;
  3. 每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分=被取走的元素值$*2^i$ ,其中i表示第i次取数(从1开始编号);
  4. 游戏结束总得分为m次取数得分之和。

帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。

推得转移方程

本题数据较大,需要高精度(我懒得写了用了__int128)

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
#include<cstdio>
#include<iostream>
#include<cstdlib>

using std::cin;
using std::endl;
using std::cerr;
using std::cout;
using std::max;

typedef long long LL;
typedef __int128 int128;

const int inf=0x7fffffff;
const LL linf=0x7fffffffffffffff;
const int maxn=100;

int n,m;
int a[maxn][maxn];
int128 p[maxn];
int128 dp[maxn][maxn][maxn];

void output(int128 x)
{
if(x>=10)
output(x/10);
putchar(x%10+'0');
}

int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",a[i]+j);
p[0]=1;
for(int i=1;i<=m;i++)
p[i]=p[i-1]*2;

for(int t=1;t<=n;t++)
for(int l=0;l<=m;l++)
for(int i=1,j;i<=m-l+1;i++)
{
j=i+l-1;
dp[t][i][j]=max(dp[t][i+1][j]+p[m-l+1]*a[t][i],dp[t][i][j-1]+p[m-l+1]*a[t][j]);
}

int128 ans=0;
for(int i=1;i<=n;i++)
ans+=dp[i][1][m];
output(ans);
puts("");
return 0;
}

总结例题规律,一般的区间dp问题为两两合并形式,求合并后最后两个部分的最优值。

如区间[i,j]可以通过[i,k][k+1,j]两部分合并得到,k为区间[i,j]的划分点。

转移方程一般一般为: