跳转至

区间 DP

250323 模拟赛 T3

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

\(n\le 500\)。

若区间中存在多于一个不合法的位置，则无解；若恰好有一个，则在第一次操作时删除任意一个即可。现在考虑初始没有相邻数字相等的情况。

注意到正序做不好处理，考虑时光倒流，删除变为插入。注意到插入一个数字后，两侧还没被插入的数字就已经被分隔开，不会再相邻了。因此考虑区间 dp，我们枚举区间中最先插入的元素，设 \(f[i][j]\) 表示区间 \([i,j]\)，\(i-1\) 和 \(j+1\) 都已经被插入，删光的方案数。

转移时需要判掉 \(a[k]=a[i-1]\) 以及 \(a[k]=a[j+1]\) 的情况，式子形如一个组合数。

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

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

代码 
 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
#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;
}

P5336 [THUSC 2016] 成绩单

有 \(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\}) \]

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

考虑区间 dp。注意到一次操作删除的数在原序列中不一定连续，因此考虑最后一次操作。

t1:  ...++..++++...++...++[+]
     .+..+....+++..++.+...[+]
     g[i][j - 1] add a[j]
t2:  ...++..++++...++...++++[.......]
     g[i][k] + f[k + 1][j]

图：最后一次操作删除的数字在原序列上一些可能的位置

根据区间 dp 的经典技巧，设 \(f[i][j]\) 表示删光区间 \([i,j]\) 的最小代价，\(g[i][j][\ldots]\) 表示删除区间中一些数字，还剩一些数字（作为最后一次删除）的最小代价。然后尝试通过转移来拼出最后一次删除的所有可能性。

我们注意到，区间 \([i,j]\) 中最后一次操作的所有可能性可以分成两类：删除的数字包含区间右端点、删除的数字不包含区间右端点。因此，\(g[i][j]\) 可以从 \(g[i][j-1]\) 转移，然后将 \(a[r]\) 加入状态，表示区间右端点放在最后一次删除；也可以直接从 \(g[i][k]+f[k+1][j]\) 转移，表示区间右端点在最后一次操作之前删除。

最后，我们需要执行最后一次操作，从 \(g[i][j]\) 向 \(f[i][j]\) 转移，这需要我们能从 \(g\) 记录的状态中快速计算删除剩下数字的代价（也就是最后一次删除的代价）。注意到代价只和最大值、最小值有关，因此在 \(g\) 中额外开两个状态记录它们即可。因此，\(g[i][j][mn][mx]\) 表示删除区间中一些数字，还剩一些数字，最小值为 \(mn\)，最大值为 \(mx\) 的最小代价。

转移如下：

\[ \begin{align*} &g[i][j-1][mn][mx]\to g[i][j]\bigl[\min(mn,a[j])\big]\bigl[\max(mx,a[j])\big]\\ &g[i][k][mn][mx]+f[k+1][j]\to g[i][j][mn][mx]\\ &g[i][j][mn][mx]+w(mn,mx)\to f[i][j] \end{align*} \]

值域很大，离散化即可。

代码 
 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
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 55;
const int INF = 0x3f3f3f3f;

inline void trans(int &a, int b) { a = min(a, b); }

int n, a, b;
int w[N];

int num[N], nn;

void lisanhua() {
    for(int i = 1; i <= n; i++) num[++nn] = w[i];
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) w[i] = lower_bound(num + 1, num + 1 + nn, w[i]) - num;
}

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];

    lisanhua();

    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j++) {
            f[i][j] = INF;
            for(int mn = 1; mn <= nn; mn++) {
                for(int mx = 1; mx <= nn; mx++) {
                    g[i][j][mn][mx] = INF;
                }
            }
        }
    }

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

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

    cout << f[1][n] << '\n';

    return 0;
}

P2135 方块消除

给定一个颜色序列，每次你可以删除一个长度为 \(x\) 的相同颜色段，并获得 \(x^2\) 的分数；删除之后，序列两边变为相邻。问删空序列得到的最大分数。

颜色段数不超过 \(50\)，序列总长度不超过 \(1000\)。

考虑区间 dp。对于此种删除区间问题，考虑最后一次操作会处理哪些数字。这里和上一题相似，记 \(f[i][j]\) 表示删光区间的代价，\(g[i][j][\ldots]\) 表示还剩一些数字，代价可由剩下的状态计算得到。

注意到计算最后一次操作的代价需要记录剩下数字的个数，合并状态时还需要记录剩下数字的颜色，状态数达到 \(50\times 50\times 1000\times 50=1.25\times 10^8\)，再算上转移的复杂度，不能通过。

考虑最后一次操作删掉的数字：

...++..+++....+++..

注意到我们可以枚举右侧第一个被删除的数字位置（断点），这样左半区间的右端点就钦定在最后一次删除了，其颜色也随之确定。

现在，我们设 \(g[i][j][x]\) 表示区间 \([i,j]\) 中，钦定保留右端点，一共保留 \(x\) 个颜色相同的数字，最大得分是多少。转移时我们讨论左端点即可。

\[ \begin{align*} &g[i+1][j][x]\to g[i][j][x+1]\\ &f[i][k]+g[k+1][j][x]\to g[i][j][x] \end{align*} \]
代码 
 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
#include<iostream>
using namespace std;
const int N = 55;
const int M = 1010;
const int INF = 0x3f3f3f3f;

inline void trans(int &a, int b) { a = max(a, b); }

int n, m;
int a[N], b[N];
int f[N][N], g[N][N][M];

int main() {

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

    for(int i = 1; i <= n; i++) m += b[i];

    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j++) {
            f[i][j] = -INF;
            for(int c = 0; c <= m; c++) g[i][j][c] = -INF;
        }
    }

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

    for(int len = 2; len <= n; len++) {
        for(int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for(int c = 0; c <= m; c++) {
                if(a[i] == a[j] && c >= b[i]) trans(g[i][j][c], g[i + 1][j][c - b[i]]);
                for(int k = i; k < j; k++) {
                    trans(g[i][j][c], f[i][k] + g[k + 1][j][c]);
                }
            }
            for(int k = i; k <= j; k++) {
                for(int c = 0; c <= m; c++) {
                    trans(f[i][j], g[i][k][c] + c * c + f[k + 1][j]);
                }
            }
        }
    }

    cout << f[1][n] << '\n';

    return 0;
}

CF150D Mission Impassable

给定一个字符串，你可以删掉长度为 \(i\) 的回文子串，获得 \(v_i\) 的分数，\(v_i=-1\) 代表不能删除长度为 \(i\) 的串，删除之后前后两部分变为相邻，求最多能获得多少分数。

\(|s|\le 150\)

考虑区间 dp，仍然考虑最后一次删除哪些数字。对于区间 \([i,j]\) 注意到要么 \(s_i=s_j\) 并在最后一次作为回文串的两端一起删除，要么其中一端包含一个连续的未在最后一次删除的段。因此有三个转移：

\[ \begin{align*} &g[i+1][j-1][c]\to g[i][j][c+1]\ \text{ for }\ s[i]=s[j]\\ &g[i][k][c]+f[k+1][j]\to g[i][j][c]\\ &f[i][k]+g[k+1][j][c]\to g[i][j][c]\\ \end{align*} \]

以及

\[ \begin{align*} &g[i][j][c]+v_c\to f[i][j]\\ &f[i][k]+f[k+1][j]\to f[i][j] \end{align*} \]
代码 
 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
#include<iostream>
using namespace std;
const int N = 155;
const int INF = 0x3f3f3f3f;

int n;
int a[N];
char s[N];

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

int main() {

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

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

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

    for(int len = 2; len <= n; len++) {
        for(int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for(int k = 1; k <= len; k++) {
                for(int l = i; l < j; l++) g[i][j][k] = max(g[i][j][k], max(g[i][l][k] + f[l + 1][j], g[l + 1][j][k] + f[i][l]));
                if(k >= 2 && s[i] == s[j]) g[i][j][k] = max(g[i][j][k], g[i + 1][j - 1][k - 2]);
                f[i][j] = max(f[i][j], g[i][j][k] + a[k]);
            }
            for(int k = i; k < j; k++) {
                f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j]);
            }
            g[i][j][0] = f[i][j];
        }
    }

    for(int i = 1; i <= n; i++) h[i][i] = max(0, f[i][i]);
    for(int len = 2; len <= n; len++) {
        for(int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            h[i][j] = max(h[i + 1][j], h[i][j - 1]);
            for(int k = i; k < j; k++) h[i][j] = max(h[i][j], h[i][k] + h[k + 1][j]);
            h[i][j] = max(h[i][j], f[i][j]);
        }
    }

    cout << h[1][n] << '\n';

    return 0;
}