POJ 2955——Brackets【区间DP】_综合

题目传送门

Description

We give the following inductive definition of a “regular brackets” sequence:

the empty sequence is a regular brackets sequence,
if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
if a and b are regular brackets sequences, then ab is a regular brackets sequence.
no other sequence is a regular brackets sequence
For instance, all of the following character sequences are regular brackets sequences:

(), [], (()), ()[], ()[()]

while the following character sequences are not:

(, ], )(, ([)], ([(]

Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence.

Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

Input

The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

Output

For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

Sample Input

((()))
()()()
([]])
)[)(
([][][)
end

Sample Output

6
6
4
0
6

题意：

用以下方式定义合法的括号字符串

1、空串是合法的
2 、果S是合法的, 那么(S)和[S]也都是合法的
3、如果A和B是合法的, 那么AB是一个合法的字符串.

举个栗子, 下列字符串都是合法的括号字符串:

(), [], (()), ([]), ()[], ()[()]

下面这些不是:

(, [, ), )(, ([)], ([(]

给出一个由字符’(’, ‘)’, ‘[’, 和’]'构成的字符串. 你的任务是找出一个最长的合法字符串的长度，使这个的字符串是给出的字符串的子序列。对于字符串a1 a2 … an, b1 b2 … bm 当且仅当对于1 = i1 < i2 < … < in = m, 使得对于所有1 = j = n，aj = bij时, aj是bi的子序列

题解：

定义dp [ i ] [ j ] 为串中第 i 个到第 j 个括号的最大匹配数目

1.如果第 i 个和第 j 个匹配,则dp [ i ] [ j ] = dp [ i+1 ] [ j-1 ] + 2 ;
2.如果第 i 个和第 j 个不匹配，枚举中间分割点k(i <= k < j)
dp[ i ] [ j ] = max ( dp [ i ] [ j ] , dp [ i ] [ k ] + dp [ k+1 ] [ j ] )

AC-Code：

#include <iostream>
#include <vector>
#include <utility>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <fstream>
#include <set>
using namespace std;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long ll;const int INF = 0x7fffffff;
const int MAXN = 120;int dp[MAXN][MAXN];// 区间i->j匹配数
string s;
bool check(char a, int b)
{
    if (a == '(' && b == ')') return true;else if (a == '[' && b == ']') return true;else return false;
}
int main() {
    ios;while (cin >> s) {
    if (s == "end")break;memset(dp, 0, sizeof(dp));for (int len = 2; len <= s.length(); len++)for (int i = 0; i <= s.length(); i++) {
    int j = i + len - 1;if (j > s.length())break;if (check(s[i], s[j]))dp[i][j] = dp[i + 1][j - 1] + 2;for (int k = i + 1; k < j; k++) {
    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j]);}}cout << dp[0][s.length() - 1] << endl;}return 0;
}