程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 例題9

例題9

編輯：關於C++

1.題目描述：點擊打開鏈接

2.解題思路：本題要求添加盡量少的括號，使得括號序列是一個正規序列。定義d(i,j)表示子串S[i...j]至少需要添加幾個括號。根據題意，可知有兩種轉移方式：

（1）如果S形如(S‘)或[S'],則轉移到d(S')；

（2）如果S至少有兩個字符，則可以分成AB，轉移到d(A)+d(B)；

邊界是：S為空時，d(S)=0，S為單字符時，d(S)=1,。注意不管S是否滿足第一條，都要嘗試第二種轉移方式。否則"[][]"會被轉移到"]["，然後只能加兩個括號了。本題打印的時候需要重新檢查哪個決策最好。好處是節約空間，壞處是打印時代碼比較復雜，速度較慢。但由於只有少數需要打印，因此基本可以忽略不計。

3.代碼：

#define _CRT_SECURE_NO_WARNINGS 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define maxn 200+10
int T, n;
string S;
int d[maxn][maxn];//表示S[i...j]至少需要填上幾個括號（閉區間）
bool match(char p, char q)
{
	if (p == '('&&q == ')')return true;
	if (p == '['&&q == ']')return true;
	return false;
}
void dp()
{
	for (int i = 0; i < n; i++)
	{
		d[i + 1][i] = 0;//空串
		d[i][i] = 1;//單字符
	}
	for (int i = n - 2; i >= 0; i--)//起點逆序枚舉
	for (int j = i + 1; j < n; j++)//終點順序枚舉，保證子區間已經計算過
	{
		d[i][j] = n;
		if (match(S[i], S[j]))
			d[i][j] = min(d[i][j], d[i + 1][j - 1]);//第一種轉移方式
		for (int k = i; k < j; k++)
			d[i][j] = min(d[i][j], d[i][k] + d[k + 1][j]);//第二種轉移方式
	}
}
void print(int i, int j)//分三種獨立情況，每次都只執行一種便返回
{
	if (i>j)return;
	if (i == j)//單字符
	{
		if (S[i] == '(' || S[i] == ')')
			printf("()");
		else printf("[]");
		return;
	}
	int ans = d[i][j];
	if (match(S[i], S[j]) && ans == d[i + 1][j - 1])//第一種轉移情況
	{
		printf("%c", S[i]);
		print(i + 1, j - 1);
		printf("%c", S[j]);
		return;
	}
	for (int k = i; k < j; k++)//第二種轉移情況
	if (ans == d[i][k] + d[k + 1][j])
	{
		print(i, k);
		print(k + 1, j);
		return;
	}
}
int main()
{
	//freopen("test.txt", "r", stdin);
	cin >> T;
	getchar();
	while (T--)
	{
		getchar();
		getline(cin, S);
		n = S.length();
		dp();
		print(0, n - 1);
		puts("");
		if (T)cout << endl;
	}
	return 0;
}