Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

终于过了,区间dp

Posted by shit at 2015-07-21 09:54:58 on Problem 1141
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=108;
char s[maxn];
int dp[maxn][maxn],vis[maxn][maxn];
int max(int x,int y)
{
	if(x>y)
		return x;
	return y;
}
int check(char a,char b)
{
	if(a=='('&&b==')')
		return 1;
	if(a=='['&&b==']')
		return 1;
	return 0;
}
void printpost(int i,int j)
{
	if(i>j)
		return;
	if(i==j)
	{
		if(s[i]==')'||s[i]=='(')
			printf("()");
		else if(s[i]=='['||s[i]==']')
			printf("[]");
		else printf("%c",s[i]);
	}
	else 
	{
	if(vis[i][j]==-1)
	{
		printf("%c",s[i]);
		printpost(i+1,j-1);
		printf("%c",s[j]);
	}
	else
	{
		printpost(i,vis[i][j]+i);
		printpost(vis[i][j]+i+1,j);
	}
	}
}
int main()
{
	int i,j,k;
	gets(s);
		memset(dp,0,sizeof(dp));
		memset(vis,0,sizeof(vis));
		int len=strlen(s);
		if(len==0)
		{
			printf("\n");
			return 0;
		}
		for(i=1;i<len;i++)
		{
			if(check(s[i-1],s[i]))
			{
				dp[i-1][i]=2;
				vis[i-1][i]=-1;
			}
		}
		for(k=2;k<len;k++)
		{
			for(i=0;i+k<len;i++)
			{
				if(check(s[i],s[i+k]))
				{
					dp[i][i+k]=dp[i+1][i+k-1]+2;
					vis[i][i+k]=-1;
				}
				for(j=i;j<i+k;j++)
				{
					if(dp[i][i+k]<dp[i][j]+dp[j+1][i+k])
					{
					dp[i][i+k]=dp[i][j]+dp[j+1][i+k];
					vis[i][i+k]=j-i;
					}
				}
			}
		}
		printpost(0,len-1);
		printf("\n");
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator