poj-2955 Brackets 区间dp入门

题目链接

poj-2955 Brackets

题目

Brackets Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 10213 Accepted: 5434

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, andif 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 a₁a₂ … a_n, 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 i₁, i₂, …, i_m where 1 ≤ i₁ < i₂ < … < i_m ≤ n, a_i1a_i2 … a_im 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

Source

Stanford Local 2004

题意

给出一串由'(' ')' '[' ']'组成的字符串，定义完全匹配的意义。即子串所有的单个字符均能在该子串中找到对应的匹配位置。例：((()))。中间可以穿插，但是要求能对应匹配，例：()()()。求一个串的最长匹配子串。例：)()(，其值为2，只有子串()匹配。现在给出一个字符串，输出最长的匹配子串长度。输入"end"结束。

题解

这个题是区间dp的入门题。个人对于区间dp的理解，精髓在于如何合并区间。更为经典的堆石子问题就能体现这个操作。这个题也完全利用了分区间的思想，状态上我们定义dp[i][j]表示第i个字符到第j个字符的子串，值就是最大的匹配值。那么定义一个k，将字符串分为2个区间，2个区间分别的值加起来就是可能的最大值。所有的k的最大值就是最终答案。也就是说，我们可以得到O(n^3)的算法，枚举i、j获得区间，枚举i < k < j来分区间。

如果开头与结尾2个字符恰好能匹配，那么dp[i][j] = dp[i+1][j-1]+2是错误的。例如：()()()。)()(的值是2，而()()()的值是6，因为这样忽略了原来不匹配的部分有可能跟两端的字符匹配。所以仍然需要划分区间求解。

C++ 代码 32ms

#include<iostream> #include<vector> #include<string> #include<cmath> #include<algorithm> #include<map> #include<utility> #define TIME std::ios::sync_with_stdio(false) #define LL long long #define MAX 110 using namespace std; int dp[MAX][MAX]; int Max(int a, int b) { return a > b ? a : b; } int main() { TIME; string s; while (cin >> s) { if (s == "end") break; int len = s.size(); memset(dp, 0, sizeof(dp)); for (int i = len - 1; i > 0; i--) { for (int j = i + 1; j <= len; j++) { int m = 0; if (s[i - 1] == '(' && s[j - 1] == ')' || s[i - 1] == '[' && s[j - 1] == ']') { m = dp[i + 1][j - 1] + 2; } for (int k = i + 1; k < j; k++) { m = Max(m, dp[i][k] + dp[k][j]); } dp[i][j] = m; } } cout << dp[1][len] << endl; } system("pause"); return 0; }