括号序列 题解

Problem

定义如下规则序列（字符串）：
1.空序列是规则序列；
2.如果S是规则序列，那(S)和[S]也是规则序列；
3.如果A和B都是规则序列，那么AB也是规则序列。
例如，下面的字符串都是规则序列：
(), [], (()), ([]), ()[], ()[()]
这几个不是规则序列：
(, [, ], )(, ([()
现在，给出一些有’(’ , ‘)’ , ‘[’ , ']'组成的序列，请添加尽量少的括号，得到一个规则序列，并输出该序列的长度。

Input

输入一个有’(’ , ‘)’ , ‘[’ , ']'组成的序列，长度不超过200

Output

输出规则后的字串长度

Example Input

([(]

Example Output

6

Solution

这道题还是非常简单的。 $\mid s\mid \&lt;=200$∣s∣<=200所以 $n^3$n3能过
我们考虑区间DP
对于 $f\left[x\right]\left[y\right]$f[x][y]:
若 $x=y$x=y: $f\left[x\right]\left[y\right]=1$f[x][y]=1
若 $x+1=y$x+1=y:如果可以配对， $f\left[x\right]\left[y\right]=0$f[x][y]=0否则 $f\left[x\right]\left[y\right]=2$f[x][y]=2
其他情况：
如果 $s\left[x\right]$s[x]和 $s\left[y\right]$s[y]可以配对， 可选 $f[x+1][fy-1]$f[x+1][fy−1]
若 $s\left[x\right]=\left(或\right[$s[x]=(或[，可选 $f[x+1]\left[y\right]+1$f[x+1][y]+1
若 $s\left[y\right]=\left)或\right]$s[y]=)或]，可选 $f\left[x\right][y-1]+1$f[x][y−1]+1
枚举 $k\in [x,y)$k∈[x,y) 可选 $f\left[x\right]\left[k\right]+f[k+1]\left[y\right]$f[x][k]+f[k+1][y]

Code

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>

using namespace std;

char s[210];
int f[210][210];

inline bool match(char a, char b)
{
	return a == '(' && b == ')' || a == '[' && b == ']';
}

int main()
{
	scanf("%s", s + 1);
	int len_s = strlen(s + 1);
	for (int len = 1; len <= len_s; len++)
		for (int i = 1; i + len - 1 <= len_s; i++)
		{
			int j = i + len - 1;
			if (i == j) f[i][j] = 1;
			else if (i + 1 == j)
			{
				if (match(s[i], s[j])) f[i][j] = 0;
				else f[i][j] = 2;
			}
			else
			{
				f[i][j] = INT_MAX;
				if (match(s[i], s[j])) f[i][j] = min(f[i][j], f[i + 1][j - 1]);
				if (s[i] == '(' || s[i] == '[') f[i][j] = min(f[i][j], f[i + 1][j] + 1);
				if (s[j] == ')' || s[j] == ']') f[i][j] = min(f[i][j], f[i][j - 1] + 1);
				for (int k = i; k < j; k++)
					f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
			}
		}
	printf("%d\n", len_s + f[1][len_s]);
	
	return 0;
}