跳转至

区间 DP

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

C250323 模拟赛 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\}) \]

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

我们注意到 \(n\) 非常小，考虑 DP。我们设 \(f_{i,j}\) 表示将区间 \([i,j]\) 里的所有数字都删除的最小代价。然而我们发现，对于一段区间，我们可以先删除区间中的若干部分，再一次把剩下的都删除。这种情况无法仅通过 \(f\) 进行简单的转移。

为了处理这种情况，我们改变我们原先的状态，在 \([i,j]\) 删除之后仍然保留部分元素供后面的区间使用，然后使用新状态转移到 \(f\) 状态。

我们考虑区间 \([i,j-1]\) 向 \([i,j]\) 的转移。对于 \(w_j\)，它有几种情况：

  • 自己单独删除；
  • 自己和前面的区间 \([i,j-1]\) 中的一些元素一起删除（在区间内自己解决 \(j\) 的问题）；
  • 先保留，以后和区间 \(j\) 右边的元素一起删除；

为了方便讨论和计算，将第一种情况归于第二种情况，即 \([i,j-1]\) 中没有元素和 \(j\) 一起删除。

我们先进行一些简单的分析：

  • 对于第二种情况，设 \([i,j-1]\) 中和 \(j\) 一起删除的所有元素中，最靠左的为 \(k\)，此情况就等价于将 \([k,j]\) 区间内的所有元素全部删除（\(f_{k,j}\)）。

我们现在想要知道，如何记录保留了哪些元素，以及如何对保留的元素进行转移。

我们注意到，删除区间的代价仅和区间的两个最值有关。我们可以将最大值和最小值纳入状态。具体的，我们设 \(g_{i,j,mn,mx}\) 表示区间 \([i,j]\) 经过删除之后剩下了一些数字，最小的是 \(mn\)，最大的是 \(mx\)。

具体的，对于第二种情况：

\[ g_{i,j,mn,mx}=\min_{k\in[i,j-1]}\{g_{i,k,mn,mx}+f_{k+1,j}\} \]

这样转移，我们就可以无需考虑 \([i,k]\) 和 \([k+1,j]\) 内部是如何处理的，只需要将它们拼接即可。

对于第三种情况：

\[ \begin{cases} \min\{g_{i,j-1,mn,mx}\}\rightarrow g_{i,j,w_j,mx} ,&w_j \in [1,mn]\\ \min\{g_{i,j-1,mn,mx}\}\rightarrow g_{i,j,mn,w_j} ,&w_j \in [mx,nc]\\ \min\{g_{i,j-1,mn,mx}\}\rightarrow g_{i,j,mn,mx} ,&w_j \in [mn,mx] \end{cases} \]

通过这种状态的设置，可以容易地写出 \(g\) 向 \(f\) 的转移：

\[ f_{i,j}=\max_{mn,mx\in[1,nc]}\{g_{i,j,mn,mx}\} \]
代码 
 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
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<cstring>
#include<unordered_map>
#include<algorithm>
using namespace std;
const int N = 55;
const int INF = 0x3f3f3f3f;

int n, a, b;
int w[N];
unordered_map<int, int> mp;
int num[N], nc;

int f[N][N], g[N][N][N][N];

int main() {

    cin >> n >> a >> b;
    for(int i = 1; i <= n; i++) {
        cin >> w[i];
        num[++nc] = w[i];
    }

    sort(num + 1, num + 1 + nc);
    nc = unique(num + 1, num + 1 + nc) - (num + 1);
    for(int i = 1; i <= nc; i++) {
        mp[num[i]] = i;
    }
    for(int i = 1; i <= n; i++) {
        w[i] = mp[w[i]];
    }

    memset(f, 0x3f, sizeof(f));
    memset(g, 0x3f, sizeof(g));

    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            f[j][i] = 0;
        }
    }

    for(int i = 1; i <= n; i++) {
        g[i][i][w[i]][w[i]] = 0;
        f[i][i] = g[i][i][0][0] = a;
    }

    for(int len = 2; len <= n; len++) {
        for(int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for(int mn = w[j]; mn <= nc; mn++) {
                for(int mx = mn; mx <= nc; mx++) {
                    g[i][j][w[j]][mx] = min(g[i][j][w[j]][mx], g[i][j - 1][mn][mx]);
                }
            }
            for(int mx = w[j]; mx >= 1; mx--) {
                for(int mn = mx; mn >= 1; mn--) {
                    g[i][j][mn][w[j]] = min(g[i][j][mn][w[j]], g[i][j - 1][mn][mx]);
                }
            }
            for(int mn = 1; mn <= w[j]; mn++) {
                for(int mx = w[j]; mx <= nc; mx++) {
                    g[i][j][mn][mx] = min(g[i][j][mn][mx], g[i][j - 1][mn][mx]);
                }
            }
            for(int k = i + 1; k <= j; k++) {
                for(int mn = 1; mn <= nc; mn++) {
                    for(int mx = mn; mx <= nc; mx++) {
                        g[i][j][mn][mx] = min(g[i][j][mn][mx], g[i][k - 1][mn][mx] + f[k][j]);
                    }
                }
            }
            for(int mn = 1; mn <= nc; mn++) {
                for(int mx = mn; mx <= nc; mx++) {
                    f[i][j] = min(f[i][j], g[i][j][mn][mx] + a + b * (num[mx] - num[mn]) * (num[mx] - num[mn]));
                }
            }
        }
    }

    cout << f[1][n] << endl;

    return 0;
}