题意
给出一个由小括号喝中括号组成的括号序列，定义正规括号序列为(),[],(s),[s],其中s也是正规括号序列。求最长正规括号序列的长度。
思路
考虑区间DP，设计状态时着眼于“最后一次加括号”。
状态表示：dp[i][j] = 从 i 到 j 的（包含i,j）最长的括号序列长度。
状态转移：
- dp[i][j] = dp[i][j-1] 继承上一个区间的结果
- 令k为i,j之间的一个位置，str是给出的括号串(令下标从1开始)
- 如果str[k]与str[j]正好是一对匹配的括号，可以考虑在最后一步放这个括号，用dp[i][k] + 2 + dp[k+1][j-1]尝试更新dp[i][j]
答案：dp[1][len]
初始化：直接令整个dp数组都为0，既可以完成初始化，也可以无效化所有无效状态。
代码
|
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 |
#include <stdio.h> #include <iostream> using namespace std; const int MAXN = 105; char str[MAXN]; int len; int dp[MAXN][MAXN];//dp[from][to] = maximum rectified seq len btw from and to void solve(){ memset(dp, 0, sizeof(dp)); for(int i = len; i >= 1; i--){ dp[i][i] = 0; for(int j = i+1; j <= len; j++){ dp[i][j] = dp[i][j-1]; for(int k = i; k <= j; k++){ if ((str[k-1] == '(' && str[j-1] == ')') || (str[k-1] == '[' && str[j-1] == ']')) { dp[i][j] = max(dp[i][j],dp[i][k-1] + 2 + dp[k+1][j-1]); } } } } printf("%d\n",dp[1][len]); } int main(){ while(scanf(" %s",str) != EOF){ if(str[0] == 'e'){ break; } len = (int)strlen(str); solve(); } return 0; } |
January 22, 2016
[…] POJ 2955 Brackets：最简单的区间DP，括号序列 […]