Beyond the Void
BYVoid
Ural 1183 Brackets sequence
本文正體字版由OpenCC轉換

括號序列問題,劉汝佳黑書上的動態規劃第一題,真是經典問題。不過這道題要輸出方案。

動態規劃狀態設定 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

相關日誌