POJ 2955 Brackets
传送门：http://poj.org/problem?id=2955
题目翻译
有一个序列，包含((,),[,])这些内容。相应可以匹配，问最长可匹配符合字符串长度是多少。
题解
区间DP，DP[i][j]表示区间i~j的最长可匹配长度。然后区间DP转移即可。
代码
|
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<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> using namespace std; const int Maxn=100; char seq[Maxn+5]; int dp[Maxn+5][Maxn+5]; int Len; int Ans; inline void solve(){ Len=strlen(seq); memset(dp,0,sizeof(dp)); Ans=0; for(int len=2;len<=Len;len++){ for (int left=1;left<=Len;left++){ int right=left+len-1; if (right>Len) break; dp[left][right]=max(dp[left+1][right],dp[left][right-1]); if (seq[left-1]=='(' && seq[right-1]==')') dp[left][right]=max(dp[left][right],dp[left+1][right-1]+2); if (seq[left-1]=='[' && seq[right-1]==']') dp[left][right]=max(dp[left][right],dp[left+1][right-1]+2); for (int mid=left;mid<right;mid++){ dp[left][right]=max(dp[left][right],dp[left][mid]+dp[mid+1][right]); } Ans=max(Ans,dp[left][right]); } } printf("%d\n",Ans); } int main(){ freopen("in.txt","r",stdin); while(scanf("%s",seq)!=EOF) if (seq[0]!='e')solve(); return 0; } |
原文链接：POJ 2955 Brackets
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!