区间DP

区间DP顾名思义就是在区间上进行DP。
一般的模板为

for(int len=1;len<=n;len++)
{
    for(int l=1;l+len-1<=n;l++)
    {
        int r=l+len-1;
        for(int k=l;k<r;k++)
        {
            .....
        }
    }
}

首先区间DP问题需要给问题进行划分区间，确定问题可以由小区间来推理出来大区间。然后进行枚举即可。

首先枚举一下区间长度，因为是从小区间推理出来大区间，所以len一般是从1~n,有时不能为1~n，因为有些具体的问题区间的范围是有最小值的，比如下面有一道例题，叫做zuma（祖玛），来源好像是CF。

那么确定了咱们的区间长度怎么枚举，那么咱们就可以接着来看怎么枚举区间了，首先枚举一下左端点，然后因为咱们的最外层循环为区间长度，所以咱们区间的右端点也就确定了。这样咱们就确定了区间。

然后要进行的就是区间的划分得到更小的区间。

就需要咱们的第三重循环k变量。

状态转移方程一般为f[l][r]=max/min(f[l][r],f[l][k],f[k+1][r]+合并区间的花费);

首先，先来一波例题

关路灯

原题链接

读完题面咱们可以发现，题目说：他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯，从这句话当中可以知道，咱们的状态转移是在一个区间上进行更改转移的，细想一下，这个题可以不用划分的那么细，也就是第三重循环是可以不用的。因为咱们的转移只是一格一格的进行转移，原因是题目说明了速度为1m/s。然后就应该思考怎么去转移。

咱们可以发现要计算的是耗费的能量最少，也就是区间外的东西，最多包括区间内一点。所以咱们就可以省去咱们的区间内划分。

咱们可以设定一下状态量f[l][r][0/1],0代表站在这个区间的左边，1代表站在去区间的右边。

有了状态量，转移也就呼之欲出了。

首先咱们知道f[l][r]一定是由f[l+1][r]和f[l][r-1]转移过来的。

那么咱们的状态转移方程也就大致出来了。

最后还要加上我们的花费。难点也就是在花费的计算。

首先咱们可以知道咱们的f[l+1][r]或者f[l][r-1]在这两个区间当中的灯已经是关掉的，也就是不会消耗能量，那么咱们的消耗能量也就是除了区间当中的那些灯，剩下的能量损耗。

首先求一个前缀和sum，sum[i]表示前i个灯的功率和，这样咱们就能迅速的求出一个区间当中的功率和。

求出了区间的功率和，咱们需要用sum[n]-(sum[r]-sum[l-1]);因为咱们计算的是损耗的，而咱们求出的区间是关掉的，用总的减去关掉的也就是咱们未关掉的。

功率求出来了，需要乘时间，由于小学数学知识可以得到，老张走的距离也就是时间，因为速度为1m/s。

那么咱们就可以操着思路去写代码了。

#include<bits/stdc++.h>
using namespace std;
int f[100][100][2];
int a[100],b[100],sum[100];
int n,m;
int calc(int i,int j,int l,int r)
{
    return abs(a[j]-a[i])*(sum[n]-sum[r]+sum[l-1]);
}
int main()
{

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        sum[i]=sum[i-1]+b[i];
    }
    memset(f,10,sizeof(f));
    f[m][m][0]=0;
    f[m][m][1]=0;
    for(int len=1;len<=n;len++)
    {
        for(int l=1;l+len-1<=n;l++)
        {
            int r=l+len-1;
            f[l][r][0]=min(min(f[l][r][0],f[l+1][r][0]+calc(l,l+1,l+1,r)),f[l+1][r][1]+calc(l,r,l+1,r));
            f[l][r][1]=min(min(f[l][r][1],f[l][r-1][0]+calc(l,r,l,r-1)),f[l][r-1][1]+calc(r-1,r,l,r-1));
        }
    }
    cout<<min(f[1][n][0],f[1][n][1]);
}

下一题

zuma（祖玛）

原题链接

看完题面，这个题就是祖玛的游戏规则，也就不多说了。从小区间向大区间进行扩展。

首先考虑最小区间的情况，一个球，那肯定需要一步。再进阶考虑两个球，那也就有两种情况，一种是相同，一种是不同，那么就可以得到两方向的状态转移。相同的很明显可以直接消除，不需要时间，不同的也就需要两步。

小区间的边界情况分析完了以后，就可以往外扩展了。

咱们发现这道题目不同于上一道题目，这个题目是跟区间内部有关的，所以需要k的那层循环。

这道题目还需要注意的就是这个划分的区间长度是不能小于3的。因为1和2是咱们的边界情况。如果遍历的话会出现边界情况，会超出数组的界限。

因为咱们的状态转移方程是

方程出来就可以操着思路写代码了

#include<bits/stdc++.h>
using namespace std;
int a[550];
int f[550][550];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    memset(f,10,sizeof(f));
    for(int i=1;i<n;i++)
    {
        f[i][i]=1;
        if(a[i]==a[i+1])
        {
            f[i][i+1]=1;
        }
        else
        {
            f[i][i+1]=2;
        }
    }
    f[n][n]=1;
    for(int len=3;len<=n;len++)
    {
        for(int l=1;l+len-1<=n;l++)
        {
            int r=l+len-1;
            if(a[l]==a[r])
            {
                f[l][r]=f[l+1][r-1];
            }
            for(int k=l;k<r;k++)
            {
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
            }
        }
    }
    cout<<f[1][n];
    return 0;
}