竞极 Ace

区间DP：端点选择与匹配类型问题

1. 这类题的共同点

这些题的大区间答案由更短区间得到，但转移不一定枚举普通分割点。常见决策包括：

  • 选择当前区间的左端或右端；
  • 将某个端点与区间中的另一个位置匹配；
  • 根据两个端点是否相同，选择保留或补入字符。

2. 端点选择型：Treats for the Cows

1. 题目描述

有 nn 份零食排成一排，第 ii 份零食的初始售价为 viv_i。每天只能出售当前最左端或最右端的一份零食。第 dd 天出售的零食，售价为它的初始售价乘以 dd。求出售所有零食可以获得的最大总收入。

2. 状态定义

定义：

$$dp[l][r]=\text{把区间 }[l,r]\text{ 中的零食全部卖出所能获得的最大收入}$$

当还剩区间 [l,r][l,r] 时，已经卖出 n−(r−l+1)n-(r-l+1) 份，所以当前是第：

day=n−(r−l+1)+1=n−r+lday=n-(r-l+1)+1=n-r+l

天。

3. 状态转移

当前只能卖左端或右端：

$$dp[l][r]=\max\left(v_l\times day+dp[l+1][r],\ v_r\times day+dp[l][r-1]\right)$$

当区间只剩一份零食时，它在第 nn 天出售：

dp[i][i]=vi×ndp[i][i]=v_i\times n

4. 计算顺序与代码

转移会用到去掉一个端点后的区间，长度比当前区间少 11。因此按区间长度从小到大计算。下面代码使用全局数组，long long 用于保存可能较大的总收入。

#include <algorithm>
#include <iostream>
using namespace std;

const int MAXN = 2005;
long long value[MAXN];
long long dp[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> value[i];
    }

    for (int i = 1; i <= n; ++i) {
        dp[i][i] = value[i] * n;
    }

    for (int len = 2; len <= n; ++len) {
        int day = n - len + 1;
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            dp[l][r] = max(
                value[l] * day + dp[l + 1][r],
                value[r] * day + dp[l][r - 1]
            );
        }
    }

    cout << dp[1][n] << '\n';
    return 0;
}

循环中的 len 是当前还未出售的零食数量，因此当前出售日为 n - len + 1。长度为 11 的状态已经初始化，主循环从长度 22 开始。

时间复杂度为 O(n2)O(n^2)，空间复杂度为 O(n2)O(n^2)。

3. Brackets

1. 题目描述

给定一个只包含 (、)、[、] 的字符串。可以删除任意字符，求能留下的最长合法括号子序列的长度。合法括号序列要求每个左括号都有类型相同且顺序正确的右括号与之匹配。

输入包含多组字符串，以单独一行的 0 结束。每组数据输出一个整数。

2. 状态定义

定义：

dp[l][r]=子串 [l,r] 中最长合法括号子序列的长度dp[l][r]=\text{子串 }[l,r]\text{ 中最长合法括号子序列的长度}

空区间的答案为 00，全局数组默认值即可表示。

3. 状态转移

考察左端字符 sls_l。它可以不被选入答案；也可以和某个位置 kk 的匹配括号配成一对。

如果 sls_l 与 sks_k 是一对合法括号，那么这两个字符贡献长度 22，它们之间和右侧分别形成两个子问题：

dp[l+1][k−1]+2+dp[k+1][r]dp[l+1][k-1]+2+dp[k+1][r]

所以转移为：

$$dp[l][r]=\max\left(dp[l+1][r],\ dp[l+1][k-1]+2+dp[k+1][r]\right)$$

枚举 l<k≤rl<k\le r，只有 () 或 [] 这样的同类型括号才能匹配。

4. 代码实现

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

const int MAXN = 105;
char s[MAXN];
int dp[MAXN][MAXN];

bool match(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '[' && right == ']');
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string input;
    while (cin >> input && input != "0") {
        int n = static_cast<int>(input.size());
        for (int i = 1; i <= n; ++i) {
            s[i] = input[i - 1];
        }

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

        for (int len = 1; len <= n; ++len) {
            for (int l = 1; l + len - 1 <= n; ++l) {
                int r = l + len - 1;
                dp[l][r] = dp[l + 1][r];

                for (int k = l + 1; k <= r; ++k) {
                    if (match(s[l], s[k])) {
                        dp[l][r] = max(
                            dp[l][r],
                            dp[l + 1][k - 1] + 2 + dp[k + 1][r]
                        );
                    }
                }
            }
        }

        cout << dp[1][n] << '\n';
    }

    return 0;
}

先枚举长度，确保内部区间 [l+1,k−1][l+1,k-1] 和右侧区间 [k+1,r][k+1,r] 已经计算。每个区间还要枚举匹配位置，因此时间复杂度为 O(n3)O(n^3)，空间复杂度为 O(n2)O(n^2)。

4. 端点匹配型：P1435 回文

1. 题目描述

给定一个字符串，每次可以在任意位置插入一个字符。求至少插入多少个字符，才能使字符串变成回文串。

2. 状态定义

定义：

dp[l][r]=将子串 [l,r] 变成回文串所需的最少插入次数dp[l][r]=\text{将子串 }[l,r]\text{ 变成回文串所需的最少插入次数}

单个字符本身就是回文串，不需要插入：

dp[i][i]=0dp[i][i]=0

3. 状态转移

如果两端字符相同，它们可以作为回文串的一对端点，问题缩小为中间部分：

dp[l][r]=dp[l+1][r−1]dp[l][r]=dp[l+1][r-1]

如果两端字符不同，至少需要插入一个字符来配合其中一端。可以让左端字符在右侧补出匹配字符，也可以让右端字符在左侧补出匹配字符，取较小值：

dp[l][r]=min⁡(dp[l+1][r], dp[l][r−1])+1dp[l][r]=\min(dp[l+1][r],\ dp[l][r-1])+1

4. 代码实现

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

const int MAXN = 1005;
char s[MAXN];
int dp[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> (s + 1);
    int n = 0;
    while (s[n + 1] != '\0') {
        ++n;
    }

    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            if (s[l] == s[r]) {
                dp[l][r] = dp[l + 1][r - 1];
            } else {
                dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) + 1;
            }
        }
    }

    cout << dp[1][n] << '\n';
    return 0;
}

长度为 11 的状态由全局数组的初始值 00 表示。转移只依赖更短区间，所以从长度 22 开始递增计算。时间复杂度为 O(n2)O(n^2)，空间复杂度为 O(n2)O(n^2)。