区间DP入门

本篇目录：

（没有超链接~）

1.入门区间DP：石子合并

2.环形区间DP的处理：环形石子合并，能量项链

3.高精度区间DP：凸多边形的划分

4.一般解法总结

前言：区间DP也是线性DP的一个重要分支，他往往以区间作为“阶段”，以划分区间的方法作为“决策”。

入门区间DP：石子合并

题目描述：

设有N堆沙子排成一排，其编号为1，2，3，…，N1，2，3，dots ，N1，2，3，…，N（N≤300）（Nleq 300）（N≤300）。每堆沙子有一定的数量，可以用一个整数来描述，现在要将这N堆沙子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的数量之和，合并后与这两堆沙子相邻的沙子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，如有4堆沙子分别为 1 3 5 2 我们可以先合并1、2堆，代价为4，得到4 5 2 又合并 1，2堆，代价为9，得到9 2 ，再合并得到11，总代价为4+9+11=24，如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22；问题是：找出一种合理的方法，使总的代价最小。输出最小代价。

输入描述：

第一行一个数N表示沙子的堆数N。第二行N个数，表示每堆沙子的质量(≤1000)(leq1000)(≤1000)。

输出描述
合并的最小代价
示例1
输入

4
1 3 5 2

输出

22

思路： dp [i] [j] 表示把第i堆石子到第j堆石子合并所需要的最小代价。

因为不管怎样合并，最后一步一定是把两堆石子合并成一堆，所以我们以这个分界点在哪作为区间划分依据，假设最后是将[l,k] 和 [k,r] 两堆石子合并，状态转移方程为：

 for (int k=l;k<r;k++)
    dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);

其中s数组是前缀和数组。

进行状态转移的时候要注意for循环的顺序，一般状态转移都是先枚举区间长度，再枚举起点，根据这两个计算出终点。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=310;
int a[maxn],n;
int dp[maxn][maxn];
int s[maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)  cin>>s[i];
    for(int i=1;i<=n;i++)  s[i]+=s[i-1];

  for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            dp[l][r]=1e8;
            for (int k=l;k<r;k++)
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
        }
    }
    cout<<dp[1][n];
    return 0;
}

还有一个数据加强版的石子合并，用到 GarsiaWachs 算法，直接献上洛谷链接：传送门

环形区间DP的处理

环形石子合并 原题链接

将 nn 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。

规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 nn 及每堆的石子数，并进行如下计算：

• 选择一种合并石子的方案，使得做 n−1n−1 次合并得分总和最大。
• 选择一种合并石子的方案，使得做 n−1n−1 次合并得分总和最小。

输入格式

第一行包含整数 nn，表示共有 nn 堆石子。

第二行包含 nn 个整数，分别表示每堆石子的数量。

输出格式

输出共两行：

第一行为合并得分总和最小值，

第二行为合并得分总和最大值。

数据范围
1≤n≤2001≤n≤200

输入样例：

4
4 5 9 4

输出样例：

43
54

思路： 对于环形区间DP，我们一般把环形DP转换为长度为原来两倍再枚举分界线，这样的处理一般能保证我们能够枚举到环形DP的所有情况。

其余的就跟上面的石子合并类似了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=310;
int a[maxn],s[maxn];
int dpmax[maxn][maxn],dpmin[maxn][maxn];
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*2;i++) s[i]=s[i-1]+a[i];
    memset(dpmax,-0x3f,sizeof dpmax);
    memset(dpmin,0x3f,sizeof dpmin);
    for(int len=1;len<=n;len++)
        for(int l=1;l+len-1<=2*n;l++){
            int r=l+len-1;
            if(l==r) {
                dpmax[l][r]=dpmin[l][r]=0;
                continue;
            }

            for(int k=l;k<r;k++){
                dpmax[l][r]=max(dpmax[l][r],dpmax[l][k]+dpmax[k+1][r]+s[r]-s[l-1]);
                dpmin[l][r]=min(dpmin[l][r],dpmin[l][k]+dpmin[k+1][r]+s[r]-s[l-1]);
            }


        }
    ///枚举长度为n的区间
    int minn=0x3f3f3f3f,maxx=-0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        minn=min(minn,dpmin[i][i+n-1]);
        maxx=max(maxx,dpmax[i][i+n-1]);
    }
    cout<<minn<<endl;
    cout<<maxx<<endl;
    return 0;
}

能量项链

原题链接

题目描述

在MarsMar**s星球上，每个MarsMar**s人都随身佩带着一串能量项链。在项链上有NN颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是MarsMar**s人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为mm，尾标记为rr，后一颗能量珠的头标记为r，尾标记为nn，则聚合后释放的能量为m times r times nm×r×n（MarsMar**s单位），新产生的珠子的头标记为mm，尾标记为nn。

需要时，MarsMar**s人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设N=4N=4，44颗珠子的头标记与尾标记依次为(2,3) (3,5) (5,10) (10,2)(2,3)(3,5)(5,10)(10,2)。我们用记号⊕表示两颗珠子的聚合操作，(jj⊕kk)表示第j,kj,k两颗珠子聚合后所释放的能量。则第44、11两颗珠子聚合后释放的能量为：

(44⊕11)=10 times 2 times 3=60=10×2×3=60。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为：

((44⊕11)⊕22)⊕33）=10 times 2 times 3+10 times 3 times 5+10 times 5 times 10=71010×2×3+10×3×5+10×5×10=710。

输入格式

第一行是一个正整数N(4≤N≤100)N(4≤N≤100)，表示项链上珠子的个数。第二行是NN个用空格隔开的正整数，所有的数均不超过10001000。第ii个数为第ii颗珠子的头标记(1≤i≤N)(1≤i≤N)，当i<Ni<N时，第ii颗珠子的尾标记应该等于第i+1i+1颗珠子的头标记。第NN颗珠子的尾标记应该等于第11颗珠子的头标记。

至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

输出格式

一个正整数E(E≤2.1 times (10)^9)E(E≤2.1×(10)9)，为一个最优聚合顺序所释放的总能量。

输入输出样例

输入 #1

4
2 3 5 10

输出 #1

710

说明/提示

NOIP 2006 提高组 第一题

思路：

我们先考虑非环形的区间DP，其实跟石子合并差不多~

我们记录dp[l] [r] 为从第l个珠子到第r个珠子合并成一个珠子的所得到的能量最大值

那么可以推出：

    for(int len=2;len<=n;len++)
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            for(int k=l+1;k<r;k++)
                dp[l][r]=max(dp[l][r],dp[l][k]+dp[k][r]+a[l]*a[k]*a[r]);
        }

再把这个推广到环形就可以了

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=310;
int a[maxn];
int dp[maxn][maxn];
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    for(int len=2;len<2*n;len++)
        for(int l=1;l+len-1<=n*2;l++){
            int r=l+len-1;
            for(int k=l+1;k<r;k++)
                dp[l][r]=max(dp[l][r],dp[l][k]+dp[k][r]+a[l]*a[k]*a[r]);
        }
    int maxx=-1;
    for(int i=1;i<=n;i++)
        maxx=max(maxx,dp[i][i+n]);
    cout<<maxx;
    return 0;
}

凸多边形的划分

原题链接

给定一个具有 NN 个顶点的凸多边形，将顶点从 11 至 NN 标号，每个顶点的权值都是一个正整数。

将这个凸多边形划分成 N−2N−2 个互不相交的三角形，对于每个三角形，其三个顶点的权值相乘都可得到一个权值乘积，试求所有三角形的顶点权值乘积之和至少为多少。

输入格式

第一行包含整数 NN，表示顶点数量。

第二行包含 NN 个整数，依次为顶点 11 至顶点 NN 的权值。

输出格式

输出仅一行，为所有三角形的顶点权值乘积之和的最小值。

数据范围

N≤50N≤50,
数据保证所有顶点的权值都小于109109

输入样例：
加粗样式

5
121 122 123 245 231

输出样例：

12214884

思路：

如果我们按顺时针将顶点编号，从顶点i到顶点j的凸多边形表示为如上图；
设dp[i] [j] (i<j)表示从顶点i到顶点j的凸多边形三角剖分后所得到的最大乘积，当前我们可以枚举点k，考虑凸多边形(i,j)中剖出三角形(i,j,k)，凸多边形(i,k)，凸多边形(k,j)的最大乘积和。我们可以得到状态转移方程：(1<=i<k<j<=n)
（课件上的）

 for(int k=l+1;k<r;k++)    
    dp[l][r]=max(dp[l][r],dp[l][k]+dp[k][r]+a[l]*a[k]*a[r]);

但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过long long范围，所以还需用高精度计算。（写的我头皮发麻）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>dp[55][55];
int a[55],n;
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i <A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    ll t = 0;
    for (int i = 0; i <A.size() || t; i ++ )
    {
        if (i <(int) A.size()) t += (ll)A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    return C;
}
bool cmp(vector<int> &A, vector<int> &B){
    if(A.size()!=B.size()) return A.size()>B.size();
    int i=A.size()-1;
    while(A[i]==B[i]&&i>0) i--;
    return A[i]>B[i];
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int len=3;len<=n;len++)
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            dp[l][r]=vector<int>(35,1);///初始化
            for(int k=l+1;k<r;k++){
                vector<int> x;
                x.push_back(a[l]);
                x=mul(x,a[k]);x=mul(x,a[r]);
                x=add(x,dp[l][k]);x=add(x,dp[k][r]);
                if(cmp(dp[l][r],x)) dp[l][r]=x;
            }
        }
    for(int i=dp[1][n].size()-1;i>=0;i--) cout<<dp[1][n][i];
    return 0;
}

一般写法总结：
一般区间DP有两种写法，第一就是递归式，第二就是记忆化搜索式。

基本特征：将问题分解成为两两合并的形式。
解决方法：对整个问题设最优值，枚举合并点，将问题分解成为左右两个部分，再将左右两个部分的最优值进行合并得到原问题的最优值。
设i到j的最优值，枚举剖分（合并）点，将(i,j)分成左右两区间，分别求左右两边最优值，如下图：

状态转移方程的一般形式如下：

题目合集：信息学奥赛一本通区间DP
kuangbin专题区间DP