跳转至

区间 DP

区间 dp 的 dp 数组通常定义为区间 \([i,j]\) 的答案。有时，答案还和其它的状态因素有关，也需要加入状态。

例题

250323 模拟赛 T3

题意

给你一个序列，你每次需要删除序列中的一个元素，最后将序列删空。你需要满足任意一个时刻序列中不存在两个相邻的相等元素。问删除整个序列的合法方案数。

\(n\le 500\)。

考虑区间 dp。对于这类题，我们可以枚举区间 \([i,j]\) 中最后一个删除的元素 \(k\)。在 \(k\) 删除之前，\([i,k-1]\) 和 \([k+1,j]\) 不会相邻，这就产生了一种树形结构。

设 \(f_{i,j}\) 表示删除区间 \([i,j]\)，且左右两边分别是 \(a_{i-1}\) 和 \(a_{j+1}\) 的答案。考虑转移，我们枚举 \(k\)，并且混合两个区间的操作顺序：

\[ f_{i,j}=\sum_{k=i}^{j}{f_{i,k-1}\times f_{k+1,j}\times \binom{j-i+1}{k-i}} \]

最后输出 \(f_{1,n}\) 即可。

技巧

有些情况下，区间中最后一个处理的元素会将区间分成左右两个独立的子问题，方便我们进行转移。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#define int long long
using namespace std;
const int N = 510;
const int MOD = 998244353;

int n, ans, mul = 1;
int a[N];

int c[N][N];
int f[N][N];

signed main() {

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    int sp = 0;
    for(int i = 1; i <= n - 1; i++) {
        if(a[i] == a[i + 1]) {
            if(sp) {
                sp = -1;
                break;
            }
            sp = i;
        }
    }

    if(sp == -1) {
        cout << 0 << endl;
        return 0;
    }

    if(sp) {
        --n;
        for(int i = sp + 1; i <= n; i++) {
            a[i] = a[i + 1];
        }
        a[n + 1] = 0;
        mul = 2;
    }

    c[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        c[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
        }
    }

    for(int i = 1; i <= n; i++) f[i][i] = 1;
    for(int i = 1; i <= n + 1; i++) f[i][i - 1] = 1;
    for(int len = 2; len <= n; len++) {
        for(int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            if(a[i - 1] == a[j + 1] && a[i - 1]) continue;
            for(int k = i; k <= j; k++) {
                if(a[i - 1] == a[k] || a[k] == a[j + 1]) continue;
                f[i][j] = (f[i][j] + f[i][k - 1] * f[k + 1][j] % MOD * c[len - 1][k - i] % MOD) % MOD;
            }
        }
    }

    cout << f[1][n] * mul % MOD << endl;

    return 0;
}

/*
17
1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2
*/

Y52A 最小代价

题意

有 \(n\) 个数字（\(n\le 50\)），第 \(i\) 个数字为 \(w_i\)，每次操作你可以选择一段连续的区间 \([l,r]\)，以

\[ a+b(\max_{i\in[l,r]}\{w_i\}-\min_{i\in[l,r]}\{w_i\}) \]

的代价将此区间内的所有数字删除，删除后该区间的左右两边即变为相邻。问将所有数字都删完的最小代价是多少。

请参考我的题解