【中文题意】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; }