Beyond the Void
BYVoid
Ural 1183 Brackets sequence

括号序列问题,刘汝佳黑书上的动态规划第一题,真是经典问题。不过这道题要输出方案。

动态规划状态设定 F[i,j]表示子序列[i,j]要成为括号序列所需添加的最小括号数目。

状态转移方程 F[i,j]=Min { F[i+1,j-1] (S[i]与S[j]匹配) //剥离一层匹配的括号 F[i+1,j] + 1 (S[i]为左半括号) //在结尾添加对应的右半括号 F[i,j-1] + 1 (S[j]为右半括号) //在开头添加对应的左半括号 F[i,k] + F[k+1,j] //从第k位分裂开 }

时间复杂度 O(N^3)

在动态规划状态转移的过程中记录前驱状态与添加括号的位置,然后递归输出括号序列。

以下是程序代码

#include <iostream>

using namespace std;

const int MAX=201;
const int INF=0x7FFFFFFF;

struct T
{
	int pos,fi,fj,gi,gj;
	char addition;
};

char S[MAX];
int N;
int F[MAX][MAX];
T G[MAX][MAX];

void init()
{
	freopen("1183.in","r",stdin);
	freopen("1183.out","w",stdout);
	scanf("%s",S+1);
	N=strlen(S+1);
}

inline char opp(char a)
{
	switch(a)
	{
		case '(': return ')';
		case ')': return '(';
		case '[': return ']';
	}
	return '[';
}

void peel(int i,int j)
{
	if (i+1<=N && j-1>=1)
	{
		if ((S[i]=='(' && S[j]==')') || (S[i]=='[' && S[j]==']'))
		{
			if (F[i+1][j-1]<F[i][j])
			{
				F[i][j]=F[i+1][j-1];
				G[i][j].fi=i+1;	G[i][j].fj=j-1;	G[i][j].pos=-1;
			}
		}
	}
}

void addhead(int i,int j)
{
	if (S[j]==')' || S[j]==']')
	{
		if (F[i][j-1]+1<F[i][j])
		{
			F[i][j]=F[i][j-1]+1;
			G[i][j].fi=i;	G[i][j].fj=j-1;	G[i][j].pos=1;
			G[i][j].addition=opp(S[j]);
		}
	}
}

void addtail(int i,int j)
{
	if (S[i]=='(' || S[i]=='[')
	{
		if (F[i+1][j]+1<F[i][j])
		{
			F[i][j]=F[i+1][j]+1;
			G[i][j].fi=i+1;	G[i][j].fj=j;	G[i][j].pos=2;
			G[i][j].addition=opp(S[i]);
		}
	}
}

void split(int i,int j)
{
	for (int k=i;k<j;k++)
	{
		if (F[i][k]+F[k+1][j]<F[i][j])
		{
			F[i][j]=F[i][k]+F[k+1][j];
			G[i][j].fi=i; G[i][j].fj=k;
			G[i][j].gi=k+1; G[i][j].gj=j;
			G[i][j].pos=-2;
		}
	}
}

void dynamic()
{
	int i,j;
	for (i=N;i>=1;i--)
	{
		for (j=i;j<=N;j++)
		{
			F[i][j]=INF;
			split(i,j);
			peel(i,j);
			addtail(i,j);
			addhead(i,j);
		}
	}
}

void print(int i,int j)
{
	if (i>j) return;
	if (G[i][j].pos==-1)
	{
		putchar(S[i]);
		print(i+1,j-1);
		putchar(S[j]);
	}
	else if (G[i][j].pos==-2)
	{
		print(G[i][j].fi,G[i][j].fj);
		print(G[i][j].gi,G[i][j].gj);
	}
	else if (G[i][j].pos==1)
	{
		putchar(G[i][j].addition);
		print(G[i][j].fi,G[i][j].fj);
		putchar(S[j]);
	}
	else
	{
		putchar(S[i]);
		print(G[i][j].fi,G[i][j].fj);
		putchar(G[i][j].addition);
	}
}

int main()
{
	init();
	dynamic();
	print(1,N);
	return 0;
}

上次修改时间 2017-02-03

相关日志