信息学奥赛一本通提高篇 1572：括号配对区间类动态规划

长春高老师编程

608人浏览 · 2024-12-17 13:57:51

长春高老师编程 · 2024-12-17 13:57:51 发布

1572：括号配对

时间限制: 1000 ms 内存限制: 524288 KB

【题目描述】

Hecy 又接了个新任务：BE 处理。BE 中有一类被称为 GBE。

以下是 GBE 的定义：

空表达式是 GBE

如果表达式 A 是 GBE，则 [A] 与 (A) 都是 GBE

如果 A 与 B 都是 GBE，那么 AB 是 GBE。

【输入】

输入仅一行，为字符串 BE。

【输出】

输出仅一个整数，表示增加的最少字符数

【输入样例】

[])

【输出样例】

【提示】

数据范围与提示：

对于 100% 的数据，输入的字符串长度小于 100。

【解析】

区间动态规划，详见代码：

#include<bits/stdc++.h>
using namespace std;
string s;
int n;
int dp[1000][1000];//dp[i][j]表示从第i个字符到第j个字符最多有多少个括号可以匹配
int main() {
    cin >> s;
    n = s.length();
    for(int t = 1; t <= n - 1; t++){//枚举字符串首尾位置差（长度-1）
        for(int i = 0; i < n - t; i++) {//枚举字符串起点
            int j = i + t;//计算字符串终点
            //如果两边括号匹配
            if((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']')) {
                dp[i][j] = dp[i + 1][j - 1] + 2;//内部最大值加2
            }
            //枚举分界k
            for(int k = i; k < j; k++){
                //取最大值
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
            }
        }
    }
    cout << n - dp[0][n - 1];
    return 0;
}