6.区间与环形DP问题

我们来看一道经典的问题：【NOI1995】P1880 石子合并

题面：圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并为一堆。每次只能选择两个相邻的石子堆合并成新的一堆，并将新的一堆的石子个数记为该次合并的得分。求得分的最小值与最大值。$1\le N\le 100$。记 $a_i$ 为第 $i$ 堆石子的个数，满足 $0\le a_i\le 20$。

输入样例：

4
4 5 9 4

输出样例：

43
54

我们以求最小为例。回想一下之前的 DP 问题，都是可以用前面推出后面，或者是用小的推出大的的情况。那么我们设 $f_i$ 为前 $i$ 个石子合并的最小得分，那么 $f_i$ 和 $f_{i-1},f_{i-2},...,f_1$ 有直接的关系吗？注意到是环形的，所以合并的起点一定吗？

显然是不一定的。对于环形的问题，我们可以断环成链：将数组的长度扩大一倍，例如样例中的情况，变成：4 5 9 4 4 5 9 4。这有什么作用呢？因为在环上操作都可以将其拆分成链，而链的起点是不确定的，所以我们扩大空间，对扩大的数组进行 DP，最后再枚举区间 $[1,n],[2,n+1],...,[n,2n-1]$ 取最小值即可。这就是环形 DP 的重要想法之一：二倍空间，断环成链。

然后，就化作了非环的 DP 问题。这样如何解决呢？回顾我们之前提出的问题，发现我们很难找到一种将 $f$ 数组直接关联起来的方法。所以说我们被迫再定义一维：$f_{i,j}$ 表示区间 $[i,j]$ 合并的最小得分。

这样就容易想到方法了：如果我们先将 $[i,k]$ 合并，$[k+1,j]$ 合并，最后再合并这两堆石子就行，答案就是 $f_{i,k}+f_{k+1,j}+\sum\limits_{x=i}^{j} a_x$。如果要说优化的话，就是记录一个前缀和数组 $s_i=\sum\limits_{x=1}^{i} a_x$，则答案的式子可以化为：

$f_{i,k}+f_{k+1,j}+s_j-s_{i-1}$

对于每个 $f_{i,j}$，我们都在区间 $[i,j)$ 中枚举 $k$ 记录答案即可。

那处理 $f$ 的顺序是什么呢？注意到 $k-i,j-(k+1)$ 是比 $j-i$ 小的，所以我们可以根据 $j-i$ 从小到大排序进行枚举。

最小值的代码：

#include<bits/stdc++.h>
#define INF 2147483647
using namespace std;
const int N=205;
int n;
int a[N];
int s[N];
int f[N][N];
int ans=INF;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i+n]=a[i];
    for(int i=1;i<=2*n;i++) s[i]=s[i-1]+a[i];
    for(int len=1;len<2*n;len++)
        for(int i=1;i+len<=2*n;i++){
            f[i][j]=INF;
            int j=i+len;
            for(int k=i;k<j;k++)
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
        }
    for(int i=1;i<=n;i++) ans=min(ans,f[i][i+n-1]);
    printf("%d\n",ans);
    return 0;
}

求最大值也是类似的，请读者自行写代码。

通过上一道题的研究，我们得到：区间 DP 就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的 DP 算法。

而这种问题的核心思路，就是把这区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间。

对于环形的情况，我们首先考虑扩大一倍空间，进行断环成链的处理。

现在来做一点练习。【USACO2016公开赛】P3146 248G，P1005 矩阵取数游戏，【重庆2007省选】P4170 涂色。

练习1. 248G

一看到这道题，一定是区间 DP 没错了。所以我们定义：$f_{i,j}$ 为用第 $i$ 位到第 $j$ 位的所有元素合成的最大值。如果无法全部合成，$f_{i,j}=0$。那么容易知道最终的答案就是 $f_{i,j}$ 中最大的一个。

首先易得，初始化 $f_{i,i}=a_i$。然后对于每一个 $f_{i,j}$，枚举 $i\le k<j$，如果 $f_{i,k}=f_{k+1,j}$，即为先合并 $i$ 到 $k$，再合并 $k+1$ 到 $j$，最后合并这两个，进而 $f_{i,j}=f_{i,k}+1$。

同时在更新 $f_{i,j}$ 时，要注意 $f_{i,k}$ 和 $f_{k+1,j}$ 要率先更新。所以我们自然想到：$i$ 倒序遍历，$j$ 正序遍历。

#include<bits/stdc++.h>
using namespace std;
const int N=255;
int n;
int f[N][N];
int ans=0;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&f[i][i]);
    for(int i=n-1;i>=1;i--)
        for(int j=i+1;j<=n;j++)
            for(int k=i;k<j;k++)
                if(f[i][k]==f[k+1][j]) 
                    f[i][j]=max(f[i][j],f[i][k]+1);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            ans=max(ans,f[i][j]);
    printf("%d\n",ans);
    return 0;
}