本文主要是介绍poj2955 Brackets 区间dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| Language: Brackets
Description We give the following inductive definition of 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, …, imwhere 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence. Given the initial sequence Input The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters 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 |
题意：给定一个括号序，求找到一个序列，里面的括号两两配对，求序列的最长长度。
思路：设dp[i][j]为区间[i,j]中的最大括号数,考虑第i个括号，那么我们可以分为两种情况,(1)不考虑i,直接看dp[i+1][j]; (2)i为左括号，找到与i相匹配的右括号,设为k，分两边加起来,状态方程为：dp[i][j]=max(dp[i][j],dp[i+1][k-1]+dp[k+1][j]+2);详见程序：
记忆化搜索：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100+100;
const int inf=0x3fffffff;
char s[MAXN];
int dp[MAXN][MAXN];
void dfs(int i,int j)
{if(j<=i){dp[i][j]=0;return ;}if(dp[i][j]!=-1)return ;if(j-i==1){if((s[i]=='(' && s[j]==')')||(s[i]=='[' && s[j]==']'))dp[i][j]=2;elsedp[i][j]=0;return ;}dfs(i+1,j);dp[i][j]=dp[i+1][j];for(int k=i+1;k<=j;k++)if((s[i]=='('&&s[k]==')')||s[i]=='['&&s[k]==']'){dfs(i+1,k-1); dfs(k+1,j);dp[i][j]=max(dp[i][j],dp[i+1][k-1]+dp[k+1][j]+2);}
}
int main()
{//freopen("text.txt","r",stdin);while(~scanf("%s",s) && s[0]!='e'){int n=strlen(s);memset(dp,-1,sizeof(dp));for(int i=0;i<n;i++)dp[i][i]=0;dfs(0,n-1);printf("%d\n",dp[0][n-1]);}return 0;
}
线性：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100+10;
char s[MAXN];
int dp[MAXN][MAXN];
int main()
{//freopen("text.txt","r",stdin);while(scanf("%s",s)!=EOF&&s[0]!='e'){int n=strlen(s);memset(dp,0,sizeof(dp));for(int i=n-1;i>=0;i--)for(int j=i+1;j<n;j++){dp[i][j]=dp[i+1][j];for(int k=i+1;k<=j;k++)if((s[i]=='('&&s[k]==')')||s[i]=='['&&s[k]==']')dp[i][j]=max(dp[i][j],dp[i+1][k-1]+dp[k+1][j]+2);}printf("%d\n",dp[0][n-1]);}return 0;
}这篇关于poj2955 Brackets 区间dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
