PKU演習問メモ(6/27)

No.	問題名	問題の種類および解法	難易度
2955	Brackets	動的計画法	★★☆☆☆

2955 Brackets

問題概要

"regular brakets"とは、括弧の対応が正しい文字列をいう。

(), [], (()), ()[], ()[()]は"regular brakets"であるが、
(, ], )(, ([)], ([(]はそうではない。

100文字以下の'(',')','[',']'からなる文字列が与えられた時、
この文字列の部分文字列で（連続する部分とは限らない）最長の"regular brakets"の長さを求めよ。

解法

数週間悩んだorz
NisokuのDP版と全く同じ解法で解けるじゃないかorz

dp[s][t]にsからt文字目までの最長のregularな文字列の長さを持ち、メモ化探索をすればよい。

ソースコード

int len;
string str;
int dp[101][101];

int rec(int s,int t)
{
	if(s>=t)return 0;
	int &ret=dp[s][t];
	if(ret>=0)return ret;
	ret=0;
	for(;s<t;s++)for(int i=s;i<t;i++)
	{
		if(str[s]=='('&&str[i]==')')ret=max(ret,2+rec(s+1,i)+rec(i+1,t));
		if(str[s]=='['&&str[i]==']')ret=max(ret,2+rec(s+1,i)+rec(i+1,t));
	}
	return ret;
}

int main()
{
	while(cin>>str,str!="end")
	{
		len=str.size();
		rep(i,1+len)fill_n(dp[i],1+len,-1);
		cout<<rec(0,len)<<endl;
	}
	return 0;
}