POJ – 1141 Brackets Sequence

Posted on | In , ,

思路：
区间上的动态规划，计算区间上的失配数。如果外围区间上()[]已经配好，dp值为dp[l+1][r-1]很显然我们要做的就是把失配的括号边上添一个括号。

代码：

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define INF 1e9
#define ll long long
#define ms(a,val) memset(a,val,sizeof(a))

using namespace std;
int dp[105][105], pos[105][105];
string str;
void prints(int st, int ed) {
    if (st > ed)return;
    if (st == ed) {
        if (str[st] == '(' || str[st] == ')')cout << "()";
        else cout << "[]";
    }
    else if (pos[st][ed] == -1) {
        cout << str[st];
        prints(st + 1, ed - 1);
        cout << str[ed];
    }
    else {
        prints(st, pos[st][ed]);
        prints(pos[st][ed] + 1, ed);
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    while (cin>>str) {
        ms(dp, 0);
        for (int i = 0;i < str.length();i++) {
            dp[i][i] = 1;
        }
        for (int l = 1;l <str.length();l++) {
            for (int left = 0;left+l< str.length();left++) {
                int right = left + l;
                if ((str[left] == '('&&str[right] == ')') || (str[left] == '['&&str[right] == ']'))dp[left][right] = dp[left + 1][right - 1], pos[left][right] = -1;
                else dp[left][right] = INF;
                for (int k = left; k < right;k++) {
                    if (dp[left][k] + dp[k + 1][right] < dp[left][right])dp[left][right] = dp[left][k] + dp[k + 1][right], pos[left][right] = k;
                }
            }
        }
        prints(0, str.length() - 1);
        cout << "\n";
    }
    return 0;
}