DDOSvoid's Blog

poj 2955 Brackets

发表于 分类于
本文字数： 846 阅读时长 ≈ 1 分钟

题目描述

http://poj.org/problem?id=2955

Solution

我们令f[i][j]表示区间[i,j]中的最长合法括号序列的长度

更新答案有两种方式，分别按照这两种方式来更新即可

时间复杂度 $O(n^3)$

当区间得到的答案不是精确的时候，一定要从之前的状态继承

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 110
using namespace std;

int n, m;

char s[maxn]; 

int f[maxn][maxn];

void work() {
    memset(f, 0, sizeof f); n = strlen(s + 1); 
    for (int l = 2; l <= n; ++l)
        for (int i = 1; i + l - 1 <= n; ++i) {
            int j = i + l - 1; f[i][j] = max(f[i + 1][j], f[i][j - 1]); 
            if (s[i] == '(' && s[j] == ')') f[i][j] = f[i + 1][j - 1] + 2;
            if (s[i] == '[' && s[j] == ']') f[i][j] = f[i + 1][j - 1] + 2; 
            for (int k = i; k < j; ++k) f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j]);
        }
    cout << f[1][n] << endl; 
}

int main() {
    while (1) {
        scanf("%s", s + 1); 
        if (s[1] == 'e') break; 
        work();
    }
    return 0;
}