区间DP（学习笔记）

· · 算法·理论

P1880 [NOI1995] 石子合并

特点：

$2.$**求解：** 对于求每个区间的最优解，可以来求其子区间的最优解来合并转移，如一区间的最优解是其左右区间合并的最优解，那就合并左右子区间的最优解来求该区间的最优解 # 实现： $1.$找到题目的动态转移方程，区间$DP$多为该形式： >令$f_{i,j}$表示$i$到$j$的最小值则有： >$$$f_{i,j}=min(f_{i,j},f_{i,k}+f_{k+1,j}+cost)$$$ >这是通用基础式，不是通式，具体情况要根据题目来具体分析 $2.$根据题目要求来进行状态转移的实现 # 例题实践： 阅读题目，发现这道题围成的是一个环，那我们先从一条链开始讨论： >$1.$**找到动态转移方程：** 令$f[i][j]$为把$i$区间$j$的所有石子合并起来的最大得分，则有： >$$$f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+\sum_{t=i}^{j}a[t])$$$ >$a[i]$表示第$i$堆石子的石子数量 > >$2.$**考虑优化：**$\sum_{t=i}^{j}a[i]$可以用前缀和$sum[i]$来维护，则动态转移变为： >$$$f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1])$$$ > >$3.$**实现转移：** 因为转移的前提是已经知道其子区间$f[i][k]$和$f[k+1][j]$的值，因此我们定义一个$len$表使当前区间 $i,j$的长度，在循环枚举$i$，用$len$ 算出$j=i+len-1$。最后枚举$k$进行动态转移，复杂度为$n^3

考虑是一个环，这我们可以将整个序列复制一份到末尾，使其成为2 \times n堆石子，使第n+i堆与敌i堆相等，则其也成为了类似一个环，在经行区间dp即可

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=200;
int maxn[N][N],minn[N][N];
int a[N],sum[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    for(int i=1;i<=(n<<1);i++){
        sum[i]=sum[i-1]+a[i];
        maxn[i][i]=0;
        minn[i][i]=0;
    }
    for(int len=2;len<=n;len++){
        for(int i=1;i<=2*n-len+1;i++){
            int j=i+len-1;
            maxn[i][j]=INT_MIN;
            minn[i][j]=INT_MAX;
            for(int k=i;k<j;k++){
                maxn[i][j]=max(maxn[i][j],maxn[i][k]+maxn[k+1][j]);
                minn[i][j]=min(minn[i][j],minn[i][k]+minn[k+1][j]);
            }
            minn[i][j]+=sum[j]-sum[i-1];
            maxn[i][j]+=sum[j]-sum[i-1];
        }
    }
    int mn=INT_MAX,mx=INT_MIN;
    for(int i=1;i<=n;i++){
        mn=min(mn,minn[i][i+n-1]);
        mx=max(mx,maxn[i][i+n-1]);
    }
    cout<<mn<<"\n"<<mx;
}

练习：

1.P1220 关路灯 题解
2.P3205 [HNOI2010] 合唱队 题解
3.P4767 [IOI2000] 邮局 加强版 题解