区间DP

chengni · 2018-09-27 20:20:35 · 个人记录

区间型DP是DP的一种模型，它主要以区间的长度作为区间的阶段，使用两个坐标来记录状态，向左或向右进行扩张来完成转移，也可以说是从它的子区间中转移得来。

个人觉得这种模型可能还比较好看出来一点，而且状态设计也相差不多，都一定会维护左端点和右端点。

下面扔几道例题上来

最经典的例题自然是石子合并问题了

有 N 堆石子排成一排，其中第 i 堆石子的重量为 a_i ,每次可以选择其中相邻的两堆石子合并成一堆，形成的新石子堆的重量和消耗的体力值都是两堆石子的重量之和，求把全部 N 堆石子合并成一堆最少需要消耗多少体力。

若 l-r 区间内的石子被合并，说明 l-r 之间的每堆石子都已经被合并了，而一堆石子是由两堆石子合并来的，所以合成 f[i][j] 一定是由 f[i][k] 和f[k+1][j] 两堆石子合并来的 (i<=k<j)

也可以说，一个长度为 l 的区间一定是由长度小于它的两个（或多个）子区间转移而来的

所以我们应该将区间的长度放在第一维，保证它的传递性

然后枚举这堆石子的左端点，得到一个区间 [l,r] ，然后在区间里枚举转折点 k 的位置，进行最大值的转移

伪代码如下：

for(int i=2;i<=n;i++){//区间长度
    for(int l=1;l<=n;l++){//枚举左端点
        int r=l+i-1;
        if(r>n) break;//得到右端点，判断合法性
        for(int k=l;k<r;k++){//枚举中间点
            f[i][j]="转移内容"  
        }
    }       
}

例题 P1880石子合并

这道题和上面有一点不同，首先它需要求出最大值和最小值，其次这道题的背景是一个环，也就是说第 1 堆石子和第 n 堆石子也是挨着的，那么我们就不能用刚才的代码了。我们要用到一个小技巧

断环为链

我们将原数组复制一遍（最后一个数可以不计），然后得到了一个长度为 2*n-1 的链，我们在链上就可以按照类似的做法完成了，只需要注意总区间的长度为 n 即可。

事实上除了DP,还有一些题目也会用到断环为链的技巧。这种方法可以让你省很大事。

接下来一道例题P1063 能量项链，跟上面那道基本一个思路，都是比较经典的区间 DP 问题

第二种题型，也是需要记录区间，但是每个点进入区间的时间会影响到它的价值，其实本质上跟前一种题型一样。

例题P2858 奶牛零食

我们每次取出都只能在队列两段取，那么我们换一种思路倒过来想，先选择一个点，每次从它的左右两端放回，是不是跟这个问题一样？

那么这道题的方程就显现出来了

我们同样是枚举区间长度，区间左端点，得到了一个区间，然后我们判断这个区间是从什么地方转移过来的。

如前面的分析，想得到 f[i][j] 的方法只有两种 f[i+1][j]+w[i] f[i][j-1]+w[j]

那么我们的转移方程就出来了

初始化的时候把区间长度为 1 的情况初始一下就可以了

有一道跟这个差不多的P1005 矩形取数游戏

对于这道题，实际上每一行之间是没有干扰的，我们对于每一行进行一次跟上文差不多的 DP 就可以了

代码如下

void work(){
    for(int i=1;i<=m;i++){
        f[i][i]=a[i]*ksm(2,m);//我用的快速幂，可以使用预处理
    }
    for(int i=1;i<=m;i++){//长度
        for(int l=1;i<=m;l++){//左端点
            int r=l+i;
            if(r>m) break;
            f[l][r]=max(f[l+1][r]+a[l]*ksm(2,m-r+l),f[l][r-1]+a[r]*ksm(2,m-r+l));
        }
    }
    ans+=f[1][m];//每行的答案可以统计
}

int main() {
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[j]=read();
        }
        work();
    }
    print(ans);
    return 0;
}

由于本题答案爆 long long 了，我是用 int128 水过去的，正解是高精度乘法，有兴趣的小伙伴可以码一下。

第三种题型，你在区间的左端点和你在区间的右端点情况不同

例题 P1220 关路灯

我们设计的状态为 f[i][j][0] 表示关闭 i-j的路灯，结束位置在左端的最短耗电， f[i][j][1] 表示结束位置在右端的最短耗电

然后我们在转移过程中同时转移最左端和最右端的情况

很明显 f[i][j][0] 来源于 f[i+1][j][0] 或者 f[i+1][j][1]

而 f[i][j][1] 来源于 f[i][j-1][0] 或者 f[i][j-1][1]

计算好中间转移的差值，做好预处理，我们就可以得出转移的过程

    for(int k=2;k<=n;k++){
        for(int i=1;i+k-1<=n;i++){
            int j=i+k-1;
            int s1=sum[n]+sum[i]-sum[j],s2=(sum[n]+sum[i-1]-sum[j-1]);
            f[i][j][0]=min(f[i+1][j][0]+(a[i+1]-a[i])*s1,f[i+1][j][1]+(a[j]-a[i])*s1);
            f[i][j][1]=min(f[i][j-1][0]+(a[j]-a[i])*s2,f[i][j-1][1]+(a[j]-a[j-1])*s2);
        }
    }

最后输出的时候输出 max(f[1][n][0],f[1][n][1]) 就可以了

补充例题 P3146 248

这题和第一种差不多，我们以 f[l][r] 合并作为 l-r 能取得的最大值，然后枚举中间点，当左右区间所得值相同时进行转移。

需要注意的是最大值的答案不一定会是 f[1][n] ，所以要在转移过程中进行判断

int n=read();
    for(int i=1;i<=n;i++){
        f[i][i]=read();
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int r=i+j;
            if(r>n) break;
            for(int k=j;k<=r;k++){
                if(f[j][k]==f[k+1][r]){
                    f[j][r]=max(f[j][r],f[j][k]+1);
                }
            }
            ans=max(ans,f[j][r]);
        }
    }
    cout<<ans;

接下来是这道题的加强版 P3147 262144

由于数据范围加强了， n^2 的做法就行不通了。

利用一种类似于倍增的思想

设 f[i][j] 表示从 j 开始合并到 i 的右端点下标是多少

得到转移方程

    int n=read();
    for(int i=1;i<=n;i++){
        int d=read();
        f[d][i]=i+1;
    }
    for(int i=1;i<=60;i++){
        for(int j=1;j<=n;j++){
            if(f[i][j]==0) f[i][j]=f[i-1][f[i-1][j]];
            if(f[i][j]!=0) ans=max(ans,i);
        }
    }
    cout<<ans;
    return 0;

其实这一部分我也没有太理解，先鸽了