区间DP_牛客博客

区间 DPDP 顾名思义为在区间上进行的 DPDP ，常先计算出小区间，尔后从小区间逐渐并至大区间，得终。

对于区间 DPDP 而言，其结构往往大同小异，伪代码如下：

for(int i = 1; i <= n; ++i) { //枚举区间长度
        for(int l = i; l <= n - i + 1; ++l) {  //枚举左端点
            int r = l + i - 1;
            for(int k = l; k <= r; ++k) {     //枚举分割点
                f[l][r] = f[l][k] + f[k + 1][r] // 合并区间
                          + bulabula //这里视题目不同往往也有变化，往往是合并区间的“代价”，“收益”等等。
            }
        }
    }

还有一种写法：

for(int l = n; l >= 1; --l) { //枚举左端点
        for(int r = l + 1; r <= n; ++r) { //右端点
            for(int k = l + 1; k < r; ++k) {  //枚举分割点
                f[l][r] = f[l][k] + f[k + 1][r] + bulabula// 合并区间
        }
    }

为什么这样子是可以的呢？

考虑我们对于左端点是从右往左枚举的，当我们拿到一个新的左端点，位于它右边的所有状态都是已经被计算过的，那么显然可以正常进行状态转移。

对于区间 DPDP 的题目，不论是状态设计亦或是状态转移，均需把握好从小区间到大区间的过渡，以及转移时的代价，此之为区间 DPDP 之难点所在。

Example~first :Example first:

给定数列 aa ，每次去掉一个数（要求既不是最左边的数也不是最右边的数），打完后这个数就消失了，而得到的价值是左边第一个还没去掉的数 *∗ 右边第一个还没去掉的数 *∗ 自己的值。

首先，设计状态，按照区间 DPDP 的传统，设 f[i][j]f[i][j] 为合并了 ii 到 jj 的区间得到的最大值。

如何转移呢？

对于每次合并的价值，考虑在我们枚举每个分割点的时候，对于 ll 到 rr 的区间，我们以 kk 为分割点，我们先合并了 ii到 kk 再合并 kk 到 ii ，那么当我们合并的时候，显然是这样一种状态： kk 左边的第一个数是 l - 1l−1 ，右边第一个数是 r + 1r+1 ，贡献为 a[l - 1] * a[k] * a[r + 1]a[l−1]∗a[k]∗a[r+1]

那么转移方程也就得到了： f[i][j]=max(f[i][j],f[i][k-1]+f[k+1][j]+a[k]*a[i-1]*a[j+1]);f[i][j]=max(f[i][j],f[i][k−1]+f[k+1][j]+a[k]∗a[i−1]∗a[j+1]);

完整代码：

/*
Time:2018年12月8日20:57:02 
Author:SpXace
Place:lzyz
Type:
From:
Input:

Output:

*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define clr(a, b) memset(a, b, sizeof(a))
#define int long long
using namespace std;
inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
const int N = 5050;
int n, a[N], f[N][N];
signed main() {
    n = read();
    rep(i, 1, n) a[i] = read();
    rep(i, 2, n - 1) f[i][i] = a[i - 1] * a[i] * a[i + 1];
    rep(i, 2, n) {
        rep(l, 1, n - i + 1) {
            int r = l + i - 1;
            rep(k, l, r) f[l][r] = max(f[l][r], f[l][k - 1] + f[k + 1][r] + a[k] * a[l - 1] * a[r + 1]);
        }
    }
    printf("%lld\n", f[2][n - 1]);
    return 0;
}

Example~second:Example second:

给定一个正整数序列 a(1),a(2),...,a(n), (1<=n<=20)a(1),a(2),...,a(n),(1<=n<=20)

不改变序列中每个元素在序列中的位置，把它们相加，并用括号记每次加法所得的和，称为中间和。

例如:

给出序列是 4, 1, 2, 34,1,2,3 。

第一种添括号方法:

((4+1)+(2+3))=((5)+(5))=(10)((4+1)+(2+3))=((5)+(5))=(10)

有三个中间和是 5,5,105,5,10 它们之和为: 5+5+10=205+5+10=20

第二种添括号方法

(4+((1+2)+3))=(4+((3)+3))=(4+(6))=(10)(4+((1+2)+3))=(4+((3)+3))=(4+(6))=(10)

中间和是 3, 6, 103,6,10 ，它们之和为 1919 。

考虑状态：设 f[i][j]f[i][j] 为 ii 到 jj 的区间得到的中间值的最小值。

那么每次合并得到的价值呢？显然合并左右两个区间，对答案的贡献是区间里的所有数。用前缀和维护。

那么状态转移方程就显而易见了： f[l][r] = min(f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1]);f[l][r]=min(f[l][k]+f[k+1][r]+sum[r]−sum[l−1]);

这道题的难点还在于输出的方式，由于不在本篇的讨论范围，这里不做赘述。

/*
Time:2018年12月8日21:04:33 
Author:SpXace
Place:lzyz
Type:
From:
Input:

Output:

*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define clr(a, b) memset(a, b, sizeof(a))
using namespace std;
inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
const int N = 5050;
int n, a[N], f[N][N], lef[N], rig[N], ans[N][N], sum[N]; 
void prinf(int l, int r) {
    if(l == r) return;
    ++lef[l];
    ++rig[r];
    prinf(l, ans[l][r]);
    prinf(ans[l][r] + 1, r);
    return;
}
void print(int l, int r) {
    if(l == r) return;
    print(l, ans[l][r]);
    print(ans[l][r] + 1, r);
    printf("%d ", sum[r] - sum[l - 1]);
    return;
}
int main() {
    n = read();
    clr(f, 0x3f);
    rep(i, 1, n) {
        a[i] = read(); f[i][i] = 0;
        sum[i] = sum[i - 1] + a[i];
    }
    rep(i, 2, n) 
        rep(l, 1, n - i + 1) {
            int r = l + i - 1;
            rep(k, l, r) {
                if(f[l][r] >= f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1]) {
                    f[l][r] = f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1];
                    ans[l][r] = k;
                }
            }
        }
    prinf(1, n);
    rep(i, 1, n) {
        rep(j, 1, lef[i]) printf("(");
        printf("%d", a[i]);
        rep(j, 1, rig[i]) printf(")");
        if(i != n) printf("+");
    }
    printf("\n%d\n", f[1][n]);
    print(1, n);
    return 0;
}

总之，对于区间 DPDP 而言，状态往往比较类似，每道题的变换往往集中在合并区间时 DPDP 值的计算。而区间 DPDP的也往往具有独特的标志：通常可以抽象成一个数列，每次只能对相邻的两个对象进行操作。

Written By SpXace