区间 DP

什么是区间 DP？

区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来由很大的关系。令状态 f ( i , j ) f(i,j) f(i,j) 表示将下标位置 到 的所有元素合并能获得的价值的最大值，那么 f ( i , j ) = m a x ( f ( i , k ) + f ( k + 1 , j ) ) + c o s t ) f(i,j)=max {( f(i,k)+f(k+1,j) )}+cost ) f(i,j)=max(f(i,k)+f(k+1,j))+cost)， c o s t cost cost 为将这两组元素合并起来的代价。

区间 DP 的特点：

合并：即将两个或多个部分进行整合，当然也可以反过来；

特征：能将问题分解为能两两合并的形式；

求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

例题1.石子合并

P1880 [NOI1995]石子合并

要注意这是个环，是一个石子圈。

怕日后我自己又看不懂了就放个链接，还是很好理解的
时间复杂度 O ( 8 N 3 ) O(8N^3) O(8N3)

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)
using namespace std;
typedef long long ll;//全用ll可能会MLE，ll比int占的内存大
const ll N=1002;
const ll INF=1e9+7;
const ll mod=2147483647;
const double EPS=1e-6;
ll n,minn,f1[N][N],f2[N][N],sum[N],a[N];
inline ll dis(ll i,ll j){return sum[j]-sum[i-1];}//求j~i应该是sum[j]-sum[i-1]
int main()
{
    scanf("%lld",&n);
    over(i,1,n)
    {
        scanf("%lld",&a[i]);
        a[i+n]=a[i];//因为是个环，所以需要处理到2n
        sum[i]=sum[i-1]+a[i];
    }
    over(i,n,2*n)
    {
        a[i+n]=a[i];//因为是个环，所以需要处理到2n
        sum[i]=sum[i-1]+a[i];
    }
    //别忘了我的over是 <=
    over(p,1,n-1)//把所有的区间全部枚举一遍，取所有的子问题中的最优解
    {
        for(int i=1,j=i+p;(j<2*n)&&(i<2*n);i++,j=i+p)
        {
            f2[i][j]=INF;
            over(k,i,j-1)//把所有情况全部试一遍，所有的分组情况全部试一遍
            {
                f1[i][j]=max(f1[i][j],f1[i][k]+f1[k+1][j]+dis(i,j));//以k为分界线，把i~k和k+1~j合并并按照题意加上i~j的石子数
                f2[i][j]=min(f2[i][j],f2[i][k]+f2[k+1][j]+dis(i,j));//加上dis(i,j)，按照题意得到得分//有点Floyd的感觉
            }
        }
    }
    minn=INF;ll maxx=0;
    over(i,1,n)
    {
        maxx=max(maxx,f1[i][i+n-1]);
        minn=min(minn,f2[i][i+n-1]);
    }
    printf("%lld\n%lld\n",minn,maxx);
    return 0;
}

例题2.能量项链

【每日DP】day12、P1063 能量项链（区间DP又一模板，震惊，只需要4行代码？）难度⭐⭐⭐

有任何疑问欢迎评论哦虽然我真的很菜