@dxbdly 2020-11-21T16:04:23.000000Z 字数 21165 阅读 365

算法专题——区间DP

OI-DP

$\text{The word is from dawn_sdy}$

区间DP是最标准的一种DP，有助于我们深刻理解DP的思想。

阅读提醒：

每道例题自己思考后再看下面的分析，总结，效果会更好。

文章禁止自主转载，若需转载请与博主联系，并注明原博客地址。

一.线性模型的区间DP

先来看道板子题：

T1：合并石子

题面

$1^o$ 分析：

我们可以设： $f[i][j]$ 为从 $i$ 合并到 $j$ 的最小价值。

考虑枚举一点 $k$ ，最后一次合并在 $k$ 点进行。

状态转移方程：

$f[i][j]=\min(f[i][[k]+f[k+1][j]+sum[i][j])$

其中 $sum[i][j]$ 为 $i$ 到 $j$ 的前缀和。

代码：

#include<bits/stdc++.h>
#define int long long
#define INF INT_MAX
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
int a[105],sum[105],f[105][105];
signed main(){
    n=read();
    for (register int i=1;i<=n;++i)//读入+前缀和
        a[i]=read(),sum[i]=sum[i-1]+a[i];
    for (register int i=1;i<=n;++i)
        for (register int j=1;j<=n;++j)//初始化
            f[i][j]=INF;
    for (register int i=1;i<=n;++i)
        f[i][i]=0;
    for (register int len=2;len<=n;++len)//区间长度
        for (register int i=1;i+len-1<=n;++i)//左端点
            {
            int j=i+len-1;//计算出右端点
            for (register int k=i;k<j;++k)//枚举断点k
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
            }
    printf("%lld",f[1][n]);
    return 0;
}

$2^o$ 思考与总结

这题是一个很经典的区间DP，我们从中可以看出区间DP的经典模式：

    for (register int len=2;len<=n;++len)
        for (register int i=1;i+len-1<=n;++i)
            {
            int j=i+len-1;
            for (register int k=i;k<j;++k)
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+附加权值);

而这也体现了DP的核心思想。

初学区间DP的人肯定会有疑问为什么要先枚举区间长度？

我们来仔细看每一重循环，这三重循环，正是DP都要有的三重循环。

第一重：

    for (register int len=2;len<=n;++len)

其实这里的长度，代表的是DP中的阶段

我们想要求长度为n的，就必须把1到n-1都求出来。

也就是说，DP的第一重循环，大多枚举阶段

第二重：

    for (register int i=1;i+len-1<=n;++i)

我们已经知道了阶段就是长度，但是同样长度的区间有很多段。

而每一种长度一样的区间，对应的就是这个阶段中的状态

也就是说，这里是用枚举左端点来简洁枚举区间，也就是枚举状态。

所以，DP的第二重循环，大多枚举状态

第三重：

    for (register int k=i;k<j;++k)

我们枚举这个点k，为的是将状态转移。

而这个转移的点，一般都是到达当前状态时，最后一步产生变化的点 (当前状态从什么状态来)

那么使得状态与状态转移的点，当然就是我们DP中的决策点

也就是说，DP的第三重循环，大多枚举决策点

其实我们的所有DP几乎都枚举了，阶段+状态+决策这三个循环
只不过有些可以常数时间枚举，没有用循环呈现。

T2 248 G

题面

我们再来看道例题。

$1^o$ 分析：

可以看出此题与例题1差不太多。

我们依旧以 $f[i][j]$ 为从 $i$ 合并到 $j$ 的最小价值。

考虑枚举一点 $k$ ，最后一次合并在 $k$ 点进行。

与之前不同的是，这里的合并需要增加一个条件，只有满足：

$f[i][k]=f[k+1][j]$

才可以合并。

PS：

提一点，为什么满足这个条件就可行，我当时想到的问题是：
如果两个最大值中间被隔开了怎么办？
但显然不会有这种情况，如果被隔开，必定有一区间为0，则条件不成立。

代码：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
int a[255],f[255][255],ans;
int main(){
    n=read();
    for (register int i=1;i<=n;++i)
        a[i]=read();
    for (register int i=1;i<=n;++i)
        f[i][i]=a[i];
    for (register int len=2;len<=n;++len)
        for (register int i=1;i+len-1<=n;++i)
            {
            int j=i+len-1;
            for (register 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 (register int i=1;i<=n;++i)
        for (register int j=1;j<=n;++j)
            ans=max(ans,f[i][j]);
    printf("%d",ans);
    return 0;
}

$2^o$ 思考与总结

经过这两道例题，我们基本可以总结出区间DP的基本套路了。

如何判断题目是否要用区间DP：

从题目性质上：

满足条件：不同位置操作出来的结果不同，一般用区间DP

从题目类型上：

合并问题，拆分问题，一般用区间DP

T3 释放囚犯

题面

刚才看了两道合并问题，下面来看一个拆分问题。

$1^o$ 分析

考虑将拆分问题转化为合并问题。

我们考虑先让所有需要释放的囚犯出列。

此时总共被分成了q-1个区间。

则按照石子合并的模型建模。

则可以想象每次将一个释放的囚犯加进去，所获得的权值就是与之相邻的两个区间的和（既将相邻的两个区间合并）

状态转移方程：

$f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+(len-2)+sum[j]-sum[i-1])$

PS:

几个需要注意的细节：

1.读入需要排序，单独区间的权值计算需注意

2.我们再合并时，合并的那个点当前不能算到权值，但以后需要累加进权值。

代码：

#include<bits/stdc++.h>
#define INF INT_MAX
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,m;
int a[105],sum[105],f[105][105];
int main(){
    n=read(),m=read();
    for (register int i=1;i<=m+1;++i)
        for (register int j=1;j<=m+1;++j)
            f[i][j]=INF;
    for (register int i=1;i<=m;++i)
        a[i]=read();
    sort(a+1,a+m+1);
    for (register int i=1;i<=m;++i)
        f[i][i]=0,sum[i]=sum[i-1]+a[i]-a[i-1]-1;
    f[m+1][m+1]=0,sum[m+1]=sum[m]+n-a[m];
    for (register int len=2;len<=m+1;++len)
        for (register int i=1;i+len-1<=m+1;++i)
            {
            int j=i+len-1;
            for (register int k=i;k<j;++k)
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+(len-2)+sum[j]-sum[i-1]);
            }
    printf("%d",f[1][m+1]);
    return 0;
}

$2^o$ 思考与总结

此题透露出的思想：

1.拆分问题大多可以使用区间DP

2.遇到拆分问题等类似的正向不好处理的问题，可以考虑将其反向转化。

T4 Treats for the Cows

题面

前面的题，决策点都是在区间中枚举一个中间点，下面我们来看一道枚举两边点的题目。

$1^o$ 分析

我们第一眼其实会觉得此题可以用贪心，但实则不行，如下例子：

9 1 1 8 8 8 8 8

按贪心的思路，应该从8一直向左删，但显然不对。

那么考虑DP

我们把拿的次数当作阶段。

则状态就是拿了哪些（可以用左端点拿了多少个表示）

由于题目说只能从左右两端拿

所以决策点只有左右两端。

我们设 $f[len][i]$ 为第 $len$ 次拿，共从左边拿了 $i$ 个的最大价值。

（我的写法并不是标准的区间DP，但和区间DP殊途同归）

则枚举决策：此次拿的是左端点还是右端点。

转移方程：

$f[len][i]=max(f[len-1][i-1]+a[i]*len,f[len-1][i]+a[n-j+1]*len)$

代码：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
int a[2005],f[2005][2005],ans;
int main(){
    n=read();
    for (register int i=1;i<=n;++i)
        a[i]=read();
    for (register int len=1;len<=n;++len)
        for (register int i=0;i<=len;++i)
            {
            int j=len-i;
            f[len][i]=max(f[len-1][i-1]+a[i]*len,f[len-1][i]+a[n-j+1]*len);
            }
    for (register int i=0;i<=n;++i)
        ans=max(ans,f[n][i]);
    printf("%d",ans);
    return 0;
}

$2^o$ 思考与总结

从此题可以看出决策不一定是中间取一点，还可能只在两端决策。

T5 关路灯

题面

有的时候基础的区间DP状态不足够，此时便需要填充状态，如这一道例题。

$1^o$ 分析

考虑此题的决策点，可以发现最后把灯关完一定是在两端，由此推出决策点在两端。

设: $f[i][j]$ 为关掉 $i$ 到 $j$ 的区间的灯的最少时间。

可以发现，人上一次站在状态的左端还是右端给出的贡献不同，此时我们不好转移，那么可以考虑补充状态。

$f[i][j][0/1]$ 表示关掉 $i$ 到 $j$ 的区间的灯的最少时间，0表示在左端，1表示在右端。

可知转移方程：

$f[i][j][0]=\min{(f[i+1][j][0]+(sum[n]-sum[j]+sum[i])*(a[i+1].x-a[i].x))}$

$f[i][j][0]=\min{(f[i+1][j][1]+(sum[n]-sum[j]+sum[i])*(a[j].x-a[i].x))}$

$f[i][j][1]=\min{(f[i][j-1][0]+(sum[n]-sum[j-1]+sum[i-1])*(a[j].x-a[i].x))}$

$f[i][j][1]=\min{(f[i][j-1][1]+(sum[n]-sum[j-1]+sum[i-1])*(a[j].x-a[j-1].x))}$

代码：

#include<bits/stdc++.h>
#define INF INT_MAX
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,c;
struct node{
    int x,w;
}a[55];
int f[55][55][2],sum[55];
int main(){
    n=read(),c=read();
    for (register int i=1;i<=n;++i)
        a[i].x=read(),a[i].w=read(),sum[i]=sum[i-1]+a[i].w;
    for (register int i=1;i<=n;++i)
        f[i][i][0]=f[i][i][1]=abs(a[c].x-a[i].x)*(sum[n]-a[c].w);
    for (register int len=2;len<=n;++len)
        for (register int i=1;i+len-1<=n;++i)
            {
            int j=i+len-1,tot1=sum[n]-sum[j]+sum[i],tot2=sum[n]-sum[j-1]+sum[i-1];
            f[i][j][0]=min(f[i+1][j][0]+(a[i+1].x-a[i].x)*tot1,f[i+1][j][1]+(a[j].x-a[i].x)*tot1);
            f[i][j][1]=min(f[i][j-1][1]+(a[j].x-a[j-1].x)*tot2,f[i][j-1][0]+(a[j].x-a[i].x)*tot2);
            }
    printf("%d",min(f[1][n][0],f[1][n][1]));
    return 0;
}

$2^o$ 思考与总结

(1)当决策点不好确定时,可以考虑分析最终状态，从而推出决策点。
(2)当我们的基础状态无法将信息表示完全时，需补充状态

线性模型区间DP小结

线性模型区间DP的要点：

1.本质：不同位置作相同操作得出不同结果的题一般可用区间DP
2.分类：合并型问题与拆分型问题，可以考虑将拆分型问题改为合并型问题。
3.决策点：中间与两端，可以通过最终状态判断
4.细节1：难度大的区间DP一般同时有中间与两端的决策点，分类讨论得清晰
5.细节2：有的时候基础状态无法完全描述所需信息，需要补全状态。

二.环形区间DP

环形区间DP虽然与线性模型区间DP区别不大，但细节处理值得考虑。

T1 石子合并(NOI1995)

题面

还是先来看道模板题

$1^o$ 分析

与之前那一道石子合并的区别是此题是在一个环形上合并的。

那么此时有以下两点区别：

1.第1位与第n位可以合并
2.统计答案可以是合并1~n，(2~n,1),(3~n,1~2)等

考虑将环转化成链。

可以发现，我们将链复制一遍，接在后面，就可以达到环的效果。

统计答案时，就是统计：1~ n，2~ (n+1)，3~ (n+2)……的最大值。

化成链后用之前的DP方法即可。

代码：

#include<bits/stdc++.h>
#define INF INT_MAX
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
int a[205],sum[205],fminn[205][205],fmaxx[205][205],ans1,ans2;
int main(){
    n=read();
    for (register int i=1;i<=n;++i)
        a[i+n]=a[i]=read();
    int m=n<<1;
    for (register int i=1;i<=m;++i)
        sum[i]=sum[i-1]+a[i];
    for (register int i=1;i<=m;++i)
        for (register int j=1;j<=m;++j)
            fminn[i][j]=INF,fmaxx[i][j]=0;
    for (register int i=1;i<=m;++i)
        fminn[i][i]=fmaxx[i][i]=0;
    for (register int len=2;len<=n;++len)
        for (register int i=1;i+len-1<=m;++i)
            {
            int j=i+len-1;
            for (register int k=i;k<j;++k)
                fminn[i][j]=min(fminn[i][j],fminn[i][k]+fminn[k+1][j]+sum[j]-sum[i-1]),fmaxx[i][j]=max(fmaxx[i][j],fmaxx[i][k]+fmaxx[k+1][j]+sum[j]-sum[i-1]);
            }
    ans1=INF,ans2=0;
    for (register int i=1;i+n-1<=m;++i)
        {
        int j=i+n-1;
        ans1=min(ans1,fminn[i][j]),ans2=max(ans2,fmaxx[i][j]);
        }
    printf("%d\n%d",ans1,ans2);
    return 0;
}

$2^o$ 思考与总结

1.遇到环型问题可以考虑化环为链
2.经典方法是将链倍长(复制一边接在末尾)就可以达到环的效果

T2 能量项链

一道几乎模板的题，适合练手。

题面

$1^o$ 分析

首先倍长(输入及倍长需注意细节)

不同位置结果不同，满足区间DP

考虑设状态： $f[i][j]$ 表示合并 $i$ 到 $j$ 的区间收获的最大价值

枚举当前区间最后一次合的点 $k$ ，方程：

$f[i][j]=\max{(f[i][j],f[i][k]+f[k+1][j]+a[i].pre*a[k].nex*a[j].nex)}$

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,m;
struct node{
    int pre,nex;
}a[205];
int f[205][205],ans;
signed main(){
    n=read();
    for (register int i=1;i<=n;++i)
        a[i-1].nex=a[i+n-1].nex=a[i+n].pre=a[i].pre=read();
    a[n].nex=a[n<<1].nex=a[1].pre;
    m=n<<1;
    for (register int i=1;i<=m;++i)
        f[i][i]=0;
    for (register int len=2;len<=n;++len)
        for (register int i=1;i+len-1<=m;++i)
            {
            int j=i+len-1;
            for (register int k=i;k<j;++k)
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i].pre*a[k].nex*a[j].nex);
            }
    for (register int i=1;i+n-1<=m;++i)
        ans=max(ans,f[i][i+n-1]);
    printf("%lld",ans);
    return 0;
}

T3 Polygon

题面

此题难点在于状态的设计与转移，一道好题。

$1^o$ 分析

显然区间DP，还是倍长。

考虑设计状态。

来看一种错误的状态设计方法：

$f[i][j]$ 表示 $i$ 到 $j$ 经过计算的最大值。

考虑为何不能这样设计。

因为有负数，且有乘法，而乘法能改变正负！

也就是说，有可能有一点 $k$ ，让 $i$ 到 $k$ ， $(k+1)$ 到j结果是最小的，且为负数，最后一步出来的结果反而最大，而前面的状态并不能考虑到这种情况。

分析一下，显然可以发现，我们只需要知道两值，最大值，最小值。

所以我们设两个状态：

$fmaxx[i][j]$ 表示 $i$ 到 $j$ 的最大值， $fminn[i][j]$ 表示 $i$ 到 $j$ 的最小值。

考虑如何转移，分类讨论：

对于 $fmaxx[i][j]$ :

$(1)$ 两正数相加：

$fmaxx[i][j]=\max{(fmaxx[i][k]+fmaxx[k+1][j])}$

$(2)$ 两正数相乘：

$fmaxx[i][j]=\max{(fmaxx[i][k]*fmaxx[k+1][j])}$

$(3)$ 两负数相乘：

$fmaxx[i][j]=\max{(fminn[i][k]*fminn[k+1][j+1])}$

对于 $fminn[i][j]$ ：

$(1)$ 两负数相加：

$fminn[i][j]=\min{(fminn[i][k]+fminn[k+1][j])}$

$(2)$ 左段正数乘右段负数：

$fminn[i][j]=\min{(fmaxx[i][k]*fminn[k+1][j])}$

$(3)$ 左段负数乘右段正数：

$fminn[i][j]=\min{(fminn[i][k]*fmaxx[k+1][j])}$

最后按普通区间DP做即可：

#include<bits/stdc++.h>
#define int long long
#define INF INT_MAX
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
struct node{
    char c;
    int x;
}a[105];
int fminn[105][105],fmaxx[105][105],ans;
signed main(){
    n=read();
    for (register int i=1;i<=n;++i)
        {
        while (!isalpha(a[n+i].c=a[i].c=getchar()));
        a[n+i].x=a[i].x=read();
        }
    int m=n<<1;
    for (register int i=1;i<=m;++i)
        for (register int j=1;j<=m;++j)
            fminn[i][j]=INF,fmaxx[i][j]=-INF;
    for (register int i=1;i<=m;++i)
        fminn[i][i]=fmaxx[i][i]=a[i].x;
    for (register int len=2;len<=n;++len)
        for (register int i=1;i+len-1<=m;++i)
            {
            int j=i+len-1;
            for (register int k=i;k<j;++k)
                {
                if (a[k+1].c=='t')
                   fmaxx[i][j]=max(fmaxx[i][j],fmaxx[i][k]+fmaxx[k+1][j]),fminn[i][j]=min(fminn[i][j],fminn[i][k]+fminn[k+1][j]);
                else
                   {
                   fmaxx[i][j]=max(fmaxx[i][j],max(fmaxx[i][k]*fmaxx[k+1][j],fminn[i][k]*fminn[k+1][j]));
                   fminn[i][j]=min(fminn[i][j],min(min(fminn[i][k]*fmaxx[k+1][j],fmaxx[i][k]*fminn[k+1][j]),fminn[i][k]*fminn[k+1][j]));
                   }
                }
            }
    ans=-INF;
    for (register int i=1;i+n-1<=m;++i)
        ans=max(ans,fmaxx[i][i+n-1]);
    printf("%lld\n",ans);
    for (register int i=1;i+n-1<m;++i)
        if (fmaxx[i][i+n-1]==ans)
           printf("%d ",i);
    return 0;
}

$2^o$ 思考与总结

我们完全可以根据转移的需要灵活的设计状态，例如此题，可以发现我们最后的答案与 $fminn$ 无关，设计 $fmaxx$ 与 $fminn$ 两个数组的原因是我们分析题目性质发现转移时缺少了信息，于是开 $fminn$ 数组补充信息，有种双DP的感觉。

T4 Naptime

题面

此题的麻烦在于如何环转链。

$1^o$ 分析

考虑如何环转链。

考虑倍长，但发现一个问题，看题目中的一句话：

但是在每一段的第一个小时不能恢复体力，从第二个小时开始才可以恢复体力。

也就是说，上一天的最后一小时，会影响到这一天的第一个小时，并且答案统计的还是这一天的N个小时。

那么考虑到底如何环转链。

可以发现，其实环型的影响无非只在于上一天第 $n$ 个小时对这一天的第一个小时的影响。

那么考虑分两种情况讨论：

即上一天第 $n$ 天休息了与上一天第 $n$ 天未休息。

那么考虑线性的怎么做，这个就比较基础了。

设： $f[i][j]$ 为前 $i$ 个小时休息了 $j$ 小时的最大价值。

但是发现，信息不足，当前是否产生价值与上一个小时是否休息有关系，考虑补充状态。

设： $f[i][j][0/1]$ 为前 $i$ 个小时休息了 $j$ 个小时，并且第 $i$ 个小时休息了/没休息

则有：

$f[i][j][0]=max{(f[i-1][j][0],f[i-1][j][1])}$

$f[i][j][1]=max{(f[i-1][j-1][0],f[i-1][j-1][1]+a[j])}$

代码：

#include<bits/stdc++.h>
#define INF INT_MAX
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int t,n,b;
int a[4005],f[4005][4005][2],ans;
inline void clear()
{
    for (register int i=1;i<=n;++i)
        for (register int j=0;j<=b;++j)
            f[i][j][0]=f[i][j][1]=-INF; 
}
inline void work()
{
    for (register int i=2;i<=n;++i)
        for (register int j=0;j<=min(i,b);++j)
            {
            f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]);
            if (j)
               f[i][j][1]=max(f[i-1][j-1][1]+a[i],f[i-1][j-1][0]);
            }
}
int main(){
    t=read();
    while (t--)
          {
          memset(a,0,sizeof(a)),ans=-INF;
          n=read(),b=read();
          for (register int i=1;i<=n;++i)
              a[i]=read();
          clear(),f[1][0][0]=0,f[1][1][1]=a[1],work(),ans=max(ans,f[n][b][1]);
          clear(),f[1][0][0]=0,f[1][1][1]=0,work(),ans=max(ans,f[n][b][0]);
          printf("%d\n",ans);
          }
    return 0;
}

$2^o$ 思考与总结

从此题我们可以看出，环转链的方法并不仅仅局限于倍长，断开等，有时候也需要通过分析题目的性质，通过分类讨论等形式灵活的转换。

环形区间DP小结

1.本质：将线性模型区间DP复杂化，增加了环化链的步骤，同时也提高了题目的灵活性
2.环化链：环化链的几种常用方法：倍长，枚举环上一点从此点断开成链，根据题目性质灵活的分类讨论等。

三.区间DP练习&杂题选讲

T1 涂色

题面

在不同位置开始涂色答案不同，考虑区间DP

设： $f[i][j]$ 为 $i$ 到 $j$ 少涂色次数。

考虑决策点的位置，分析题目可发现如下性质：

若我们要涂 $l$ 到 $r$ ，且 $col[l]==col[r]$

则，我们可以在第一遍，就把l~r都涂成 $col[l]$ ，剩下的继续涂，则可得：

$f[i][j]=max{(f[i-1][j],f[i][j-1])}$

则此时决策点在两端。

而若 $col[l]!=col[r]$

则决策点在中间，枚举决策点，方程：

$f[i][j]=max{(f[i][k]+f[k+1][j])}$

代码：

#include<bits/stdc++.h>
#define INF INT_MAX
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
char s[55];
int f[55][55],n;
int main(){
    scanf("%s",(s+1));
    n=strlen(s+1);
    for (register int i=1;i<=n;++i)
        for (register int j=1;j<=n;++j)
            f[i][j]=INF;
    for (register int i=1;i<=n;++i)
        f[i][i]=1;
    for (register int len=2;len<=n;++len)
        for (register int i=1;i+len-1<=n;++i)
            {
            int j=i+len-1;
            if (s[i]==s[j])
               f[i][j]=min(f[i+1][j],f[i][j-1]);
            for (register int k=i;k<j;++k)
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            }
    printf("%d",f[1][n]);
    return 0;
}

T2 合唱队

题面

决策点显然在两端。

设： $f[i][j]$ 为组成 $i$ 到 $j$ 的理想序列的方案数。

补充状态， $f[i][j][0/1]$ 表示 $i$ 到 $j$ 的理想序列，且最后一个进的是 $i$ / $j$ 的方案数。

方程：

$f[i][j][0]+=(a[i]<a[i+1]?f[i+1][j][0]:0)$

$f[i][j][0]+=(a[i]<a[j]?f[i+1][j][1]:0)$

$f[i][j][1]+=(a[j]<a[j-1]?f[i][j-1][0]:0)$

$f[i][j][1]+=(a[j]<a[i]?f[i][j-1][1]:0)$

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
const int mod=19650827;
int n;
int a[1005],f[1005][1005][2];
signed main(){
    n=read();
    for (register int i=1;i<=n;++i)
        a[i]=read();
    for (register int i=1;i<=n;++i)
        f[i][i][0]=1;
    for (register int len=2;len<=n;++len)
        for (register int i=1;i+len-1<=n;++i)
            {
            int j=i+len-1;
            f[i][j][0]+=(a[i]<a[i+1]?f[i+1][j][0]:0),f[i][j][0]+=(a[i]<a[j]?f[i+1][j][1]:0);
            f[i][j][0]%=mod;
            f[i][j][1]+=(a[j]>a[j-1]?f[i][j-1][1]:0),f[i][j][1]+=(a[j]>a[i]?f[i][j-1][0]:0);
            f[i][j][1]%=mod;
            }
    printf("%lld",(f[1][n][0]+f[1][n][1])%mod);
    return 0;
}

T3 Zuma1

题面

考虑决策点。

如果有 $i+1$ 到 $j-1$ 为回文串，且 $a[i]==a[j]$ ，则 $i$ 到 $j$ 也一定是回文串。

则有：

$f[i][j]=\min{(len==2?1:f[i+1][j-1])}$

考虑决策点在中间时：

$f[i][j]=\min{(f[i][k]+f[k+1][j])}$

代码：

#include<bits/stdc++.h>
#define INF INT_MAX
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
int a[505],f[505][505];
int main(){
    n=read();
    for (register int i=1;i<=n;++i)
        a[i]=read();
    for (register int i=1;i<=n;++i)
        for (register int j=1;j<=n;++j)
            f[i][j]=INF;
    for (register int i=1;i<=n;++i)
        f[i][i]=1;
    for (register int len=2;len<=n;++len)
        for (register int i=1;i+len-1<=n;++i)
            {
            int j=i+len-1;
            if (a[i]==a[j])
               f[i][j]=min(f[i][j],(len==2?1:f[i+1][j-1]));
            for (register int k=i;k<j;++k)
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            }
    printf("%d",f[1][n]);
    return 0;
}

T4 Zuma2

题面

此题的状态与转移都不好定。

首先可以发现决策点在两端或中间。

而状态显然有这样两维： $f[l][r]$ 表示 $l$ 到 $r$ 的最小花费。

考虑需要知道的信息。

当前加了多少珠子，分别加在哪里
当前如何消除，既如何转移。

而显然可以看出，如果第一条信息解决了，第二条信息就会相对好解决很多。

那么如何解决呢？

考虑设： $f[l][r][i]$ 为 $l$ 到 $r$ 的区间，在 $l$ 前面加了 $i$ 个珠子的最小花费。

则所有加的珠子都可用通过我们决策时的区间进行贡献。（如果看不懂这句可以看代码理解，大致就是转移的时候多个区间的 $k$ 合并起来）

考虑转移：

决策点在两端：

若 $i+1>=k$ ：

$f[l][r][i]=f[l+1][r][0]$

否则：

$f[l][r][i]=f[l][r][i+1]+1$

决策点在中间：

$f[l][r][i]=\min{(f[l+1][p-1][0]+f[p][r][0])}$

考虑到转移顺序较为混乱，采用记忆化搜索

#include<bits/stdc++.h>
#define INF INT_MAX
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,k;
int a[105];
int f[105][105][105];
inline int search(int l,int r,int i)
{
    if (f[l][r][i]!=-1)
       return f[l][r][i];
    if (r<l)
       return 0;
    int tot=INF;
    if (i+1>=k)
       tot=search(l+1,r,0);
    else
       tot=search(l,r,i+1)+1;
    for (register int j=l+1;j<=r;++j)
        if (a[l]==a[j])
           tot=min(tot,search(l+1,j-1,0)+search(j,r,i+1));
    f[l][r][i]=tot;
    return tot;
}
int main(){
    memset(f,-1,sizeof(f));
    n=read(),k=read();
    for (register int i=1;i<=n;++i)
        a[i]=read();
    search(1,n,0);
    printf("%d",f[1][n][0]);
    return 0;
}

T5 字符串折叠

题面

考虑决策点，两端或中间。

状态：为普通状态 $f[i][j]$ 表示 $i$ 到 $j$ 区间的最小花费。

先考虑特殊情况，假如 $x$ 最多为2（折叠次数）。

则考虑若 $a[l-1]==a[r+1]$ 且 $l$ 到 $r$ 一种折叠，则显然有 $f[l-1][r+1]=f[l][r]$

那么 $x$ 为其他值时我们也会有类似的结论。

我们判断此区间是否能折叠，如果可以则是一个在两端决策状态(类似)

这里注意贡献值的算法（详细见代码）,设 $num[i]$ 为数字 $i$ 的位数，则贡献为 $num[i]+2$ （2表示两个括号）

则如果能折叠：

$f[i][j]=\min{(f[i][k]+num[len/l]+2)}$

中间决策点：

$f[i][j]=\min{(f[i][k]+f[k+1][j])}$

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
char s[105];
int f[105][105],num[105];
inline void ready()
{
    for (register int i=1;i<=n;++i)
        f[i][i]=1;
    for (register int i=1;i<=n;++i)
        num[i]=num[i/10]+1;
}
inline bool check(int l,int r,int len)
{
    for (register int i=l;i<=r;++i)
        for (register int j=i;j<=r;j+=len)
            if (s[j]!=s[i])
               return 0;
    return 1;
}
signed main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    memset(f,0x3f,sizeof(f));
    ready();
    for (register int len=1;len<=n;++len)
        for (register int i=1;i+len-1<=n;++i)
            {
            int j=i+len-1;
            for (register int k=i;k<j;++k)
                {
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
                int l=k-i+1;
                if (len%l)
                   continue;
                if (check(i,j,l))
                   f[i][j]=min(f[i][j],f[i][k]+num[len/l]+2);
                }
            }
    printf("%d",f[1][n]);
    return 0;
}

T6 Sue的小球

题面

考虑决策点，考虑全部取完时，人必定站在左端点或右端点。

则决策点在两端。

考虑状态：

错误状态：

设： $f[i][j][0/1]$ 表示 $i$ 到 $j$ 的最大价值，且站在 $i$ / $j$

为何错误？

不好转移！由于我们走路的时候所有彩蛋都在往下掉，你是不好计算权值的。

正确状态如何设？

设： $f[i][j][0/1]$ 表示 $i$ 到 $j$ 的最小浪费，且站在 $i$ / $j$ 。

为何这么设就可以了？区别在哪？

错误的状态对于所有点算的是贡献，而这里算的是一个浪费值，看似没什么区别，我们接着看。

由于只在两端点转移，我们完全可以算除了 $l$ 到 $r$ 区间（当然也要除去当前跑的这个点）的下落速度前缀和，当前乘上花费的时间。

为什么错误状态不能这么做？

可以发现，错误状态只关心 $l$ 到 $r$ 区间内的点的贡献，忽略了其他点下落的信息。

而我们这一个状态，将跑完此区间，整个的浪费都记录下来了。

update:
看见网上一种解释方式，错误算法的错误点可以理解为：曾经的行走花费的时间会对当前的得分产生影响。
而对于这种“当前‘行动’的费用 的一部分需要在之前决策时 被计算并以状态的形式 对当前状态造成影响”的问题
我们应该记住：对于当前决策影响未来的问题，解决方法就是现在算将来的影响再进行DP

转移方程：

$f[i][j][0]=\min{(f[i+1][j][0]+(sum[i]+sum[n]-sum[j])*(a[i+1].x-a[i].x))}$

$f[i][j][0]=\min{(f[i+1][j][1]+(sum[i]+sum[n]-sum[j])*(a[j].x-a[i].x))}$

$f[i][j][1]=\min{(f[i][j-1][0]+(sum[i-1]+sum[n]-sum[j-1]])*(a[j].x-a[i].x))}$

$f[i][j][1]=\min{(f[i][j-1][1]+(sum[i-1]+sum[n]-sum[j-1])*(a[j].x-a[j-1].x))}$

代码：

#include<bits/stdc++.h>
#define int long long
#define INF INT_MAX
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,x0;
struct Point{
    int x,y,v;
}a[1005];
int f[1005][1005][2],t[1005][1005][2],ans,sum[1005];
inline bool operator <(Point x,Point y)
{
    return x.x<y.x;
}
signed main(){
//  freopen("2466.in","r",stdin);
//  freopen("2466.out","w",stdout);
    n=read(),x0=read();
    for (register int i=1;i<=n;++i)
        a[i].x=read();
    for (register int i=1;i<=n;++i)
        a[i].y=read(),ans+=a[i].y;
    for (register int i=1;i<=n;++i)
        a[i].v=read();
    a[++n].x=x0;
    sort(a+1,a+n+1);
    for (register int i=1;i<=n;++i)
        sum[i]=sum[i-1]+a[i].v;
    for (register int i=1;i<=n;++i)
        for (register int j=1;j<=n;++j)
            f[i][j][0]=f[i][j][1]=INF;
    for (register int i=1;i<=n;++i)
        if (a[i].x==x0&&!a[i].v)
           f[i][i][0]=f[i][i][1]=0;
    for (register int len=2;len<=n;++len)
        for (register int i=1;i+len-1<=n;++i)
            {
            int j=i+len-1,cnt1=sum[i]+sum[n]-sum[j],cnt2=sum[i-1]+sum[n]-sum[j-1];
            f[i][j][0]=min(f[i+1][j][0]+cnt1*(a[i+1].x-a[i].x),f[i+1][j][1]+cnt1*(a[j].x-a[i].x));
            f[i][j][1]=min(f[i][j-1][0]+cnt2*(a[j].x-a[i].x),f[i][j-1][1]+cnt2*(a[j].x-a[j-1].x));
            }
    printf("%0.3lf",(double)(ans-min(f[1][n][0],f[1][n][1]))/1000.0);
    return 0;
}

T7 Coloring Brackets

题面

我之前设的状态： $f[i][j][0/1/2][0/1/2]$ 表示 $i$ 到 $j$ 的串（不一定为完整的括号串），且后面两维表示 $i$ ， $j$ 的染色情况(0不染，1红色，2蓝色)

会有什么问题呢？首先并不完整的括号串显然没有价值（完全没必要求），其次，这样会导致我们不知道当前串中哪一部分是完整的括号串，也就没法转移(由于有第2个条件)

更好的设法：考虑设 $f[i][j][0/1/2][0/1/2]$ 为 $i$ 到 $j$ 的完整括号串，且记录 $i$ ， $j$ 染色情况。

首先把括号匹配求出来，用 $p[i]$ 表示 $i$ 对应的括号。

分三种情况：

$1^o$ $i+1==j$ : 边界情况。

$f[i][j][0][1]=f[i][j][0][2]=f[i][j][1][0]=f[i][j][2][0]=1$

$2^o$ $p[l]==r$ : 整个是个大括号(单一括号组成)

这部分方程请见代码。

$3^o$ $p[l]!=r$ :多个括号连接而成

方程见代码。（不是很好描述）

转移较为散乱，采用记记忆化搜索。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
const int mod=1e9+7;
char s[705];
int n;
int f[705][705][3][3];
int st[705],top,p[705];
inline void ready()
{
    for (register int i=1;i<=n;++i)
        if (s[i]=='(')
           st[++top]=i;
        else
           p[i]=st[top],p[st[top--]]=i;
}
inline void search(int l,int r)
{
    if (l+1==r)
       {
       f[l][r][0][1]=f[l][r][0][2]=f[l][r][1][0]=f[l][r][2][0]=1;
       return ;
       }
    if (p[l]==r)
       {
       search(l+1,r-1);
       for (register int x=0;x<=2;++x)//枚举染色状态，再将不成立的状态去除，省略了很多方程，比较巧妙。
           for (register int y=0;y<=2;++y)
               {
               if (y!=1)
                  f[l][r][0][1]=(f[l][r][0][1]+f[l+1][r-1][x][y])%mod;
               if (y!=2)
                  f[l][r][0][2]=(f[l][r][0][2]+f[l+1][r-1][x][y])%mod;
               if (x!=1)
                  f[l][r][1][0]=(f[l][r][1][0]+f[l+1][r-1][x][y])%mod;
               if (x!=2)
                  f[l][r][2][0]=(f[l][r][2][0]+f[l+1][r-1][x][y])%mod;
               }
       }
    else
       {
       int k=p[l];
       search(l,k),search(k+1,r);
       for (register int x1=0;x1<=2;++x1)//4个变量分别为i,k,k+1,j的染色状态
           for (register int x2=0;x2<=2;++x2)
               for (register int y1=0;y1<=2;++y1)
                   for (register int y2=0;y2<=2;++y2)
                       {
                       if ((!x1&&!x2)||(x2==y1&&x2))//不成立状态
                          continue;
                       f[l][r][x1][y2]=(f[l][r][x1][y2]+(f[l][k][x1][x2]*f[k+1][r][y1][y2])%mod)%mod;
                       }
       }
}
signed main(){
//  freopen("CF149D.in","r",stdin);
//  freopen("CF149D.out","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    int ans=0;
    ready(),search(1,n);
    for (register int i=0;i<=2;++i)
        for (register int j=0;j<=2;++j)
            ans=(ans+f[1][n][i][j])%mod;
    printf("%lld",ans%mod);
    return 0;
}

四.总结

大致解题步骤：

$Step1$ 辨析：

如何判断一道题是否用区间DP

从数据范围：n一般100（3次方算法），有时也能到1000
从题目类型：合并问题与拆分问题
从题目性质：大区间可以拆分成多个小区间计算，不同位置做相同操作结果不同

$Step2$ 分类：

1.按模型分类：

线性模型：经典转移f[i][j]=min(f[i][k]+f[k+1][j]+val)，val为贡献
环形模型：注意巧妙转环为链，方法一般有：倍长，枚举一点断开，根据题目性质分类讨论等

2.按题目类型分类：

合并类问题：经典模型石子合并。
拆分类问题：倒序转化为合并类问题

3.按决策点分类

决策点在中间
决策点在两边：这种情况需注意题目的性质，一般有特殊转移。
我们可以通过最终状态来确定决策点位置，很多时候两种方案都可行

$Step3$ 细节：

有一些值得注意的细节：

关于状态

经典状态f[i][j]表示i到j的区间的最大收益
很多时候需要根据题目需求或性质补充描述，要保证没有信息遗漏
灵活的设计状态，比如双DP等经典技巧

五.The end

区间DP是一种非常标准也非常基础的DP，有助于我们体会与理解DP的思想。

本文也举出了非常多的例题，当然也包括我个人的一些小小的思考。

希望对大家有帮助，感谢阅读。

$Thank$

$Q.E.D$

算法专题——区间DP

一.线性模型的区间DP

T1：合并石子

1^o 分析：

2^o 思考与总结

T2 248 G

1^o 分析：

2^o 思考与总结

T3 释放囚犯

1^o 分析

2^o 思考与总结

T4 Treats for the Cows

1^o 分析

2^o 思考与总结

T5 关路灯

1^o 分析

2^o 思考与总结

二.环形区间DP

T1 石子合并(NOI1995)

1^o分析

2^o 思考与总结

T2 能量项链

1^o 分析

T3 Polygon

1^o 分析

2^o 思考与总结

T4 Naptime

1^o 分析

2^o 思考与总结

环形区间DP小结

三.区间DP练习&杂题选讲

T1 涂色

T2 合唱队

T3 Zuma1

T4 Zuma2

T5 字符串折叠

T6 Sue的小球

T7 Coloring Brackets

四.总结

Step1 辨析：

Step2 分类：

Step3 细节：

五.The end

内容目录

选择主题

$1^o$ 分析：

$2^o$ 思考与总结

$1^o$ 分析：

$2^o$ 思考与总结

$1^o$ 分析

$2^o$ 思考与总结

$1^o$ 分析

$2^o$ 思考与总结

$1^o$ 分析

$2^o$ 思考与总结

$1^o$ 分析

$2^o$ 思考与总结

$1^o$ 分析

$1^o$ 分析

$2^o$ 思考与总结

$1^o$ 分析

$2^o$ 思考与总结

$Step1$ 辨析：

$Step2$ 分类：

$Step3$ 细节：