poj2955

发表于 | 分类于 | 阅读数 次

链接:poj2955

题解

  • DP[i][j]表示区间i~j的最大括号匹配数量,显然str[i]与str[j]如果匹配DP[i][j]=DP[i+1][j-1]+2
  • 并且对于区间i~j-1内的k必然有DP[i][j]=max(DP[i][j],DP[i][k]+DP[k+1][j])
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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=107;
int dp[N][N],n;
char str[N];
int main(){
	while(~scanf("%s",str+1)){
		if(strcmp(str+1,"end")==0)break;
		memset(dp,0,sizeof(dp));
		n=strlen(str+1);
		rep(l,2,n)rep(i,1,n-l+1){
			int j=i+l-1;
			if((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[j]==']'))dp[i][j]=dp[i+1][j-1]+2;
			rep(k,i,j-1)dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
		}
		printf("%d\n",dp[1][n]);
	}
	return 0;
}