【5】区间类型动态规划学习笔记

w9095 · 2022-12-20 10:02:00 · 算法·理论

前言

教练阳了，这次上的是录播课（悲

希望教练早点好起来

区间DP

区间DP，字面上讲，就是以一个区间为状态进行转移的动态规划。

在这类动态规划中，一般设状态 dp[i][j] 表示区间 [i,j] 的答案。

区间DP的题目的特征：

$2$ ：答案可以由两个子区间合并得到。 ![](https://cdn.luogu.com.cn/upload/image_hosting/bv7js46l.png) **区间DP的流程：** $1$ ：枚举区间，即枚举 $dp[i][j]$ 的 $i,j$ 。 $2$ ：枚举分割点 $k$ ，把原区间分割成 $[i,k]$ 和 $[k+1,j]$ 或 $[i,k-1]$ 和 $[k,j]$ 两个区间。 $3$ ：区间DP转移方程通式： $$dp[i][j]=\max/\min\{dp[i][j],dp[i][k]+dp[k+1][j]+w(i,j,k)\}$$ 模板如下： ```cpp for(int l=2;l<=n;l++) for(int i=0;i+l-1<n;i++) { int j=i+l-1; for(int k=i+1;k<=j;k++) f[i][j]=min(f[i][j],f[i][k-1]+f[k][j]); } ``` **区间DP的复杂度：** 基本时间复杂度： $O(n^3)

基本空间复杂度： O(n^2)

DP例题

例题 1 ：

P1063 [NOIP2006 提高组] 能量项链

设状态 dp[i][j] 表示合并区间 [i,j] 的能量珠的最大能量，则转移方程为：

dp[i][j]=\max(dp[i][j],dp[i][k-1]+dp[k][j]+a[i]*a[k]*a[j+1])

其中 k 为枚举聚合第 k-1 颗珠子和第 k 颗珠子。 dp[i][j] 表示不合并； dp[i][k-1] 表示合并区间 [i,k-1] ，也就是这次合并之前的区间的最大能量， dp[k][j] 表示合并区间 [k,j] ，也就是这次合并之后的区间的最大能量。 a[i]*a[k]*a[j+1] 是题目中给出能量的计算式子，直接加入即可。

还有一个小细节：由于是一个环，需要破环成链。可以通过开两倍内存，把第 i 个数在第 n+i 的位置再存一边，实现化环为链。

或者看看我的这篇博客零碎知识点整理

#include <bits/stdc++.h>
using namespace std;
int n,max1[600][600],a[20000],maxa; 
int main()
{
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            a[n+i]=a[i];
        }
    for(int i=n*2-1;i>=0;i--)
        for(int j=i+1;j<=2*n-1;j++)
            for(int k=i+1;k<=j;k++)
                max1[i][j]=max(max1[i][j],max1[i][k-1]+max1[k][j]+a[i]*a[k]*a[j+1]);
    for(int i=0;i<n;i++)maxa=max(maxa,max1[i][i+n-1]);
    printf("%d",maxa);
    return 0;
}

例题 2 ：

CF607B Zuma

设状态 dp[i][j] 表示消除区间 [i,j] 的数字的最少次数，则转移方程为：

dp[i][j]=\min(dp[i][j],dp[i+1][j-1])(a[i]==a[j])

dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k][j])

其中 k 为枚举把原区间划分为区间 [i,k-1] 和 [k,j] 的分割点。

第一个转移方程中，考虑回文串的性质，如果区间 [i,j] 左端点和右端点相等，则一定可以把它们留在消除区间 [i+1,j-1] 的最后一次消除中一起消除，故可以转移，求最小值。

第二个转移方程中，整个区间的值可以由消除分割点左边区间的次数加上消除分割点右边区间的次数，这样就能保证消除完。而消除分割点左边区间的次数是 dp[i][k-1] ，消除分割点右边区间的次数是 [k,j] ，最后加和求最小值即可。

#include <bits/stdc++.h>
using namespace std;
int n,f[600][600];
int a[600];
int main()
{
    scanf("%d",&n); 
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    for(int i=0;i<n;i++)f[i][i]=1,f[i+1][i]=1;
    for(int l=2;l<=n;l++)
        for(int i=0;i+l-1<n;i++)
            {
                int j=i+l-1;
                f[i][j]=99999999;
                if(a[i]==a[j])f[i][j]=min(f[i][j],f[i+1][j-1]);
                for(int k=i+1;k<=j;k++)
                    f[i][j]=min(f[i][j],f[i][k-1]+f[k][j]);
            }
    printf("%d",f[0][n-1]);
    return 0;
}

例题 3 ：

P1005 [NOIP2007 提高组] 矩阵取数游戏

首先，由于各行独立，可以各行分别计算。

设状态 dp[i][j] 表示取完区间 [i,j] 的数字的最大得分，则转移方程为：

dp[i][j]=2\times\max(dp[i+1][j]+a[i],dp[i][j-1]+a[j])

其中 dp[i+1][j]+a[i] 表示在这个区间的最后一次取数中，取最左边的数，就把原区间分成了 dp[i+1][j] 和 a[i] 两段。 dp[i][j-1]+a[j] 表示在这个区间的最后一次取数中，取最右边的数，就把原区间分成了 dp[i][j-1] 和 a[j] 两段。

注意：每行取数的得分 = 被取走的元素值 \times 2^i ，所以每次转移还要乘以 2 。

由于数字太大，需要开 __int128

#include <bits/stdc++.h>
using namespace std;
int n,m;
__int128 ans,a[20000],f[1020][1020];
inline __int128 read()
{
    __int128 x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

void print(__int128 x)
{
    if(x>9)print(x/10);
    putchar(x%10+'0');
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int k=0;k<n;k++)
        {
            for(int i=0;i<m;i++)
                a[i]=read();
            for(int i=0;i<=m;i++)
                for(int j=0;j<=m;j++)
                    f[i][j]=0;
            for(int len=1;len<=m;len++)
                for(int l=0;l<=m-len;l++)
                    {
                    int r=l+len-1;
                    f[l][r]=2*max(f[l+1][r]+a[l],f[l][r-1]+a[r]);
                    }
            ans+=f[0][m-1];
        }
    print(ans);
    return 0;
}

例题 4 ：

2183: 【一本通提高区间类动态规划】分离与合体（站外题，提供题面展示）

时间限制: 1 Sec 内存限制: 128 MB

Judge Mode:Std IO

题目描述

经过在机房里数日的切磋，LYD从杜神牛那里学会了分离与合体，出关前，杜神牛给了他一个测试......

杜神牛造了 n 个区域，它们紧邻着排成了一行，编号 1\sim n 。在这每个区域里都放着一把OI界的金钥匙，每一把都有一定的价值，LYD当然想得到它们了。然而杜神牛规定LYD不可以一下子把它们全部拿走，而是每次只可以拿一个。为了尽快的拿到所有的金钥匙，LYD自然就用上了刚学的分离与合体特技。

一开始LYD可以选择从 1\sim n-1 的任何一个区域(记为 K )进入，进入后LYD会在 K 区域发生分离，从而分离为两个小LYD。分离完成的同时会有一面墙在 K 和 K+1 区域之间升起，从而把 1\sim k 和 k+1\sim n 阻断为两个独立的区间。然后两个小LYD分别进入 1\sim k 和 k+1\sim n，并在各自的区间内任选除了区间末尾区域以外(即 1\sim k 或 k+1\sim n )的任何一个区域再次发生分离，就一共有了 4 个小小LYD……重复进行以上所叙述的分离，直到每个小LYD发现自己所在的区间只剩下了一个区域，他们就可以抱起自己梦寐以求的OI金钥匙。

但是LYD不能就这么分成 n 多个个体存在于世界上，这些小LYD还会再合体，合体的两个小LYD所在的区间中间的墙会消失。合体会获得一定的价值，计算方法是：

(合并后所在区间的最左端区域和最右端区域里金钥匙的价值之和) 乘 (之前分离的时候所在区域的金钥匙价值)。

例如：LYD曾经在 1\sim3区间中的 2 号区域分离成为 1\sim2 和 3 两个区间，合并时获得的价值就是（ 1号金钥匙价值+ 3 号价值）*( 2 号金钥匙价值)。

LYD请你编程求出最终可以获得的总价值最大是多少。并按照分离阶段从前到后，区域从左向右的顺序，输出发生分离的区域编号 (例如：先打印 1 分为 2 的分离区域，然后从左到右打印 2 分为 4 的分离区域，然后是 4 分为 8 的......) 。

注意：若有多种方案，选择分离区域尽量靠左的方案（也可以理解为输出字典序最小的）。

输入

第一行:正整数 n (2\le n\le300)

第二行: n 个正整数，表示 1\sim n 区域里每把金钥匙的价值。

保证答案及运算过程中不超出longint范围。

输出

第一行一个数，即获得的最大价值

第二行按照分离阶段从前到后，区域从左向右的顺序，输出发生分离的区域编号，中间用一个空格隔开，若有多种方案，选择分离区域尽量靠左的方案（也可以理解为输出字典序最小的）。

输入输出样例

样例输入

7
1 2 3 4 5 6 7

样例输出

238
1 2 3 4 5 6

提示

对于 20\% 的数据， n\le10

对于 40\% 的数据， n\le50

对于 100\% 的数据， n\le300,a_{i}\le300

类似能量项链（不用破环成链），易得转移方程：

dp[i][j]=\max(dp[i][j],dp[i][k-1]+dp[k][j]+(a[i]+a[j])*a[k-1])

注意需要横向输出路径，可以记录分割点 pre[i][j] ，每次使用分割点计算出分割成的两个区间，使用类似广度优先搜索遍历即可。

#include <bits/stdc++.h>
using namespace std;
int n,max1[600][600],a[20000],maxa,pre[600][600],mi,mj;
void out(int ii,int jj)
{
    int fx[100000],fy[100000],head=0,tail=0;
    fx[++head]=ii;
    fy[++tail]=jj;
    while(head<=tail)
        {
        int i=fx[head];int j=fy[head];
        if(pre[i][j]!=0)
           {
           printf("%d ",pre[i][j]);
           fx[++tail]=i;fy[tail]=pre[i][j]-1;
           fx[++tail]=pre[i][j];fy[tail]=j;
           }
        head++;
        }
}

int main()
{
    scanf("%lld",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    for(int i=n-1;i>=0;i--)
        for(int j=i+1;j<=n-1;j++)
            for(int k=i+1;k<=j;k++)
                if(max1[i][k-1]+max1[k][j]+(a[i]+a[j])*a[k-1]>max1[i][j])
                   {
                   max1[i][j]=max1[i][k-1]+max1[k][j]+(a[i]+a[j])*a[k-1];
                   pre[i][j]=k;
                   }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(i!=j&&max1[i][j]>maxa)maxa=max1[i][j],mi=i,mj=j;
    printf("%d\n",maxa);
    out(mi,mj);
    return 0;
}

后记

讲得非常好的一篇区间DP题解

扩展博客：区间DP