HDU5479 – Scaena Felix(简单DP)

【中文题意】HDU5479

【分析】dp[i][j]表示前0~i个字符串，最后一个是j( 0-‘(‘, 1-‘)’ )全部没有匹配时的最小花费。

那么转移方程就是:dp[i][0] = min(dp[i-1][0],dp[i-1][1])+(‘)’ == s[i]);dp[i][1] = dp[i-1][1]+(‘(‘ == s[i]);

以'(‘结尾时，i-1个随便什么都可以，所以选择小的那个，而’)’结尾时只能选择’)’否则就要改变它。

【AC CODE】0ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
#include <bitset>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 1000+10;
int dp[MAXN][2];
char s[MAXN];

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%s", s);
		int len = strlen(s);
		clc(dp,0);
		dp[0]['(' == s[0]] = 1;
		rep(i,1,len)
		{
			dp[i][0] = min(dp[i-1][0],dp[i-1][1])+(')' == s[i]);
			dp[i][1] = dp[i-1][1]+('(' == s[i]);
		}
		printf("%d\n",min(dp[len-1][0],dp[len-1][1]));
	}
	return 0;
}