紫书例题 9-10 UVa 1626 (区间dp + 输出技巧）

当前区间f(i, j)分两种情况，一种是s[i]于s[j]符合要求，那么可以转移到f[i + 1][j - 1] 这样答案只会更小或者相等

第二种是直接分成两个部分，即f[i][j] = f[i][k] + f[k + 1][j]，这个时候要取min

同时要注意第一种情况未必是最优的，要从一二两种情况里面取最优值

然后输出方面，按照答案反推，如果当前状态刚好等于其中一种情况，那么就递归下去，边界是

一个字符的时候输出两个字符。

另外学会用fgets，不用gets。fgets头文件cstdio， fgets(s, MAXN, stdin);

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112;

char s[MAXN];

int f[MAXN][MAXN], n;

inline bool match(char a, char b)

{

	return (a == '(' && b == ')') || (a == '[' && b == ']');

}

void work()

{

	REP(i, 0, n)

	{

		f[i + 1][i] = 0;

		f[i][i] = 1;

	}

	for(int i = n - 1; i >= 0; i--)

		REP(j, i + 1, n)

		{

			f[i][j] = n;

			if(match(s[i], s[j])) f[i][j] = f[i + 1][j - 1];

			REP(k, i, j)

				f[i][j] = min(f[i][j], f[i][k] + f[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 = f[i][j];

	if(match(s[i], s[j]) && ans == f[i + 1][j - 1])

	{

		putchar(s[i]);

		print(i + 1, j - 1);

		putchar(s[j]);

		return;

	}

	REP(k, i, j)

		if(ans == f[i][k] + f[k + 1][j])

		{

			print(i, k); print(k + 1, j);

			return;

		}

}

void read(char* s)

{

	fgets(s, MAXN, stdin);

}

int main()

{

	int T;

	scanf("%d", &T);

	read(s); read(s);

	while(T--)

	{

		read(s);

		n = strlen(s) - 1;

		work();

		print(0, n -1);

		puts("");

		if(T) puts("");

		read(s);

	}

	return 0;

}

巴特西

紫书例题 9-10 UVa 1626 (区间dp + 输出技巧）

最新文章

热门文章

巴特西

紫书 例题 9-10 UVa 1626 (区间dp + 输出技巧）

最新文章

热门文章

紫书例题 9-10 UVa 1626 (区间dp + 输出技巧）