TopCoder SRM 301 Div2 Problem 1000 CorrectingParenthesization（区间DP）

题意给定一个长度为偶数的字符串。这个字符串由三种括号组成。

　　现在要把这个字符串修改为一个符合括号完全匹配的字符串，改变一个括号的代价为$1$，求最小总代价。

区间DP。令$dp[i][j]$为把子序列$[i,j]$修改为符合要求的括号序列。

其中$cnt$为调整当前最外层的那对括号所需的最小代价。

那么有状态转移方程$dp[i][j] = min(dp[i+1][j-1] + cnt, min(dp[i][k] + dp[k+1][j]))$

用记忆化搜索实现。

#include <bits/stdc++.h>

using namespace std;

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

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

const int N = 53;

int f[N][N];

int a[N];

int n;

int dp(int l, int r){

	if (l > r) return 0;

	if (~f[l][r]) return f[l][r];

	int cnt = 0;

	if (a[l] > 0 && a[r] < 0 && a[l] + a[r] == 0) cnt = 0;

	else if (a[l] > 0 || a[r] < 0) cnt = 1;

	else cnt = 2;

	int ret = dp(l + 1, r - 1) + cnt;

	for (int i = l + 1; i <= r - 1; i += 2) ret = min(ret, dp(l, i) + dp(i + 1, r));

	return f[l][r] = ret;

}

class CorrectingParenthesization {

	public:

		int getMinErrors(string s){

			memset(f, -1, sizeof f);

			n = s.size();

			rep(i, 0, n - 1){

				if (s[i] == '(') a[i + 1] = 1;

				else if (s[i] == '[') a[i + 1] = 2;

				else if (s[i] == '{') a[i + 1] = 3;

				else if (s[i] == ')') a[i + 1] = -1;

				else if (s[i] == ']') a[i + 1] = -2;

				else if (s[i] == '}') a[i + 1] = -3;

			}

			return dp(1, n);

		}

};

巴特西

TopCoder SRM 301 Div2 Problem 1000 CorrectingParenthesization（区间DP）

最新文章

热门文章