区间dp在算法竞赛中的应用

[[ slider_text ]]

[[ item.c ]]

区间dp在算法竞赛中的应用

发布时间 2024-07-06 作者：秋千月 来源：算法小站，代码源

区间dp

## ICPC Beijing 2017 J
**[ICPC Beijing 2017 J, Pangu And Stones](https://qoj.ac/problem/8281)**
**问题描述**
给定$$n$$堆石头，每一堆有$$a_i$$个，给定$$[L, R]$$，表示相邻的连续$$k \in [L, R]$$堆石头可以合并成一堆
代价是这些堆中石头数量之和
求把$$n$$堆石头合并成一堆的最小代价，不能合成一堆输出$$0$$

### 算法分析
![](/media/content_img/interdp-01.png)
### 算法实现
```bash
void solve() {
    vector<int> a(N+1, 0), s(N+1, 0);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &a[i]);
        s[i] = s[i-1] + a[i];
    }

for (int l = 1; l <= N; l++) for (int r = 1; r <= N; r++) {
        for (int k = 1; k <= N; k++) dp[l][r][k] = inf;
    }

for (int d = 1; d <= N; d++) for (int l = 1; l+d-1 <= N; l++) {
        int r = l+d-1;
        if (d == 1) {
            dp[l][r][1] = 0;
        }
        else {
            for (int k = 2; k <= N; k++) {
                for (int mid = l; mid+1 <= r; mid++) {
                    chmin(dp[l][r][k], dp[l][mid][1] + dp[mid+1][r][k-1]);
                }

if (L <= k && k <= R) chmin(dp[l][r][1], dp[l][r][k] + s[r]-s[l-1]);
            }
        }
    }

int ans = dp[1][N][1];
    if (ans >= inf) printf("0\n");
    else printf("%d\n", ans);
}
```

## ICPC Kunming 2020 C
**[ICPC Kunming 2020 C, Cities](https://ac.nowcoder.com/acm/contest/12548/C)**
**问题描述**
给定$$n$$个城镇和$$n$$个国王，一开始第$$i$$个城镇属于第$$a_i$$个国王
每次选定一个下标连续且属于同一个国王的城镇，把这些城镇都归属到任意一个国王下面
问让所有城镇属于一个国王，最少的操作次数

实际上就是给你一个序列，每次选择连续的，$$a_i$$值都相同的段，把它改成另外一个值
最后使得所有的值都相同，问最少的操作次数

$$n \leqslant 5000$$，并且每一个数$$a_i$$出现次数不超过 15 次

### 算法分析
![](/media/content_img/interdp-02-1.png)
![](/media/content_img/interdp-02-2.png)

>  怎么快速用链表求出相等的所有位置
    可以从后往前遍历
	```bash
	for all i, let pos( a(i) ) = n+1
	for k = n down to 1
		nxt(k) = pos( a(k) )
		pos( a(k) ) = k
	```
	
### 算法实现
```bash
void solve() {
    int n, N;
    scanf("%d", &N);
    vector<int> pos(N+1, N+1), A(N+1, 0), nxt(N+1, 0);

for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
    vector<int> a;

for (int i = 1; i <= N; i++) {
        if (i == 1 || (i > 1 && A[i] != A[i-1])) a.push_back(A[i]);
    }
    n = a.size();
    a.insert(a.begin(), -1);

// a[1..n]
    for (int k = n; k >= 1; k--) nxt[k] = pos[a[k]], pos[a[k]] = k;

// dp
    vector<vector<int> > dp(n+5, vector<int> (n+5, 0));
    for (int d = 1; d <= n; d++) {
        for (int l = 1; l+d-1 <= n; l++) {
            auto r = l + d - 1;

chmax(dp[l][r], dp[l+1][r]);
            auto p = nxt[l];
            while (p <= r) {
                chmax(dp[l][r], dp[l+1][p-1] + 1 + dp[p][r]);
                p = nxt[p];
            }
            
        }
    }

int ans = n - 1 - dp[1][n];
    printf("%d\n", ans);
}
```

## CSP-S 2021 括号序列
**[括号序列](https://www.luogu.com.cn/problem/P7914)**
**问题描述**
给定由字符`(、 )、*`组成的字符串，并且给定一个常数$$k$$，定义合法的括号序列如下

* `()、(S)`均为合法括号序列，其中`S`仅有`*`字符组成，`*`字符个数不超过$$k$$个

*  `A, B`均为合法的超级括号序列，`AB, ASB`也合法

*  `A`是合法括号序列，`(A)、(SA)、(AS)`也是合法括号序列

*   空字符串不合法

换句话说，合法串连接的时候，可以在两个串中间加个`S`，另外给合法串加括号的时候，
可以在其一边（左或右）加上`S`
比如`*()、(*()*)、((**))*)、(****(*))`均不是合法括号序列
注意到左右加若干个`*`，之后需要给序列加上括号

比如`((**()*(*))*)(***)`，一开始是合法序列`()*(*)`，然后左边加入两个`**`，构成`(** ()*(*) )`
再在右边加入一个`*`，构成`( (** ()*(*) ) * )`，最后和`(***)`拼接

现在问，给定一个长度为$$n$$的括号序列，其中一些位置已经确定，另一些位置不确定
有多少种将`?`字符一一确定的方法，使得最后得到的字符串是合法的括号序列？

### 算法分析
>  一般的括号序列怎么做？

对于一般的括号序列问题，只需要保证任意位置，前缀左括号个数都$$\geqslant$$右括号个数
并且在最后的位置，左括号和右括号相等
$$dp(i, j)$$表示在第$$i$$个位置，左括号个数减去右括号的个数为$$j$$，这样就可以转移了
如果`s(i) = '(`，$$dp(i, j) \leftarrow dp(i-1, j-1)$$
否则$$dp(i, j) \leftarrow dp(i-1, j+1)$$

> 这个问题怎么做？
注意到，把串`A` 用括号括起来，只能在一边加`*`号，这个是比较麻烦的地方

![](/media/content_img/interdp-03-1.png)
![](/media/content_img/interdp-03-2.png)
![](/media/content_img/interdp-03-3.png)
![](/media/content_img/interdp-03-4.png)

**注意**，实际上，这里只需要关心第一段
* **前缀有没有连续的 `*` 号**，以此方案数划分为 `A, SA`
* 枚举前缀中 `*` 号**第一次终止的位置**，计算`SA`，即上述所说的**只切第一段**

### 算法实现
```bash
int main() {
    function<bool(int, char)> match = [&](int p, char c) -> bool {
        return str[p] == '?' || str[p] == c;
    };

for (int d = 1; d <= n; d++) {
        for (int l = 1; l + d - 1 <= n; l++) {
            int r = l + d - 1;

// case1
            if (match(l, '(') && match(r, ')') && l != r) {
                if (r == l + 1) dp[l][r] += 1;
                else if (r - l - 1 <= k) {
                    bool ok = true;
                    for (int i = l+1; i < r; i++) {
                        if (!match(i, '*')) {
                            ok = false;
                            break;
                        }
                    }

if (ok) dp[l][r] += 1;
                }

// (A)
                dp[l][r] += g[l+1][r-1];
                // (SA)
                dp[l][r] += h[l+1][r-1];
                // (AS)
                for (int i = r-1; i >= l+1 && r-i <= k; i--) {
                    if (!match(i, '*')) break;
                    dp[l][r] += g[l+1][i-1];
                }
            }

g[l][r] = dp[l][r];
            // no limit, case 2
            if (match(l, '(')) {
                for (int m = l+1; m < r; m += 1) {
                    // [l, m] = ( )
                    mint res = 0;
                    res += g[m+1][r], res += h[m+1][r];
                    g[l][r] += dp[l][m] * res;
                }
            }

// h[l][r], [l, r] = SA
            for (int i = l; i < r && i - l + 1 <= k; i++) {
                if (!match(i, '*')) break;
                h[l][r] += g[i+1][r];
            }
        }
    }

mint ans = g[1][n];
    printf("%d\n", ans.val());
}
```

## ICPC CERC 2014 L
**[ICPC CERC 2014 L, Outer Space Invaders](https://www.luogu.com.cn/problem/P4766)**
**问题描述**
有$$n$$个敌人，第$$i$$个敌人会在$$a_i$$时间出现，$$b_i$$时间消失，距离你的距离是$$d_i$$
你有一个炸弹，可以设置爆炸半径$$R$$，可以炸死$$\leqslant R$$的敌人，消耗$$R$$的燃料
你可以在任意时刻，多次放置任意范围的炸弹，问消耗燃料最少的代价是多少，能把所有敌人都消灭

### 算法分析
![](/media/content_img/interdp-04.png)
### 算法实现
```bash
int solve(int l, int r) {
    if (l > r) return 0;
    int &res = dp[l][r];
    if (res != -1) return res;

res = inf;
    int maxv = -1, p = -1;
    for (int i = 1; i <= N; i++) if (a[i] >= l && b[i] <= r) {
        if (d[i] > maxv) maxv = d[i], p = i;
    }

if (maxv == -1) return res = 0;
    for (int k = a[p]; k <= b[p]; k += 1) chmin(res, solve(l, k-1) + solve(k+1, r));
    res += maxv;
    return res;
}
```

上一篇：数位dp（二）下一篇：状态压缩动态规划（一）

看完文章有啥想法