本文主要是介绍hdu 3351 Seinfeld / poj 3991 括号匹配2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给出一个由'{' , '｝' 组成的字符串，通过改变最少括号的方向使其匹配。
思路：一开始用区间dp，TLE了，贪心才能过。贪心方法：从左向右遍历，遇到左括号lef++，遇到右括号，若lef>0，lef--，否则右括号变为左括号，ans++，lef++，最后再加上多下来的左括号，即lef/2。
先给出TLE代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=2005;
char str[maxn];
int dp[maxn][maxn], len;
int match(int x, int y){return (str[x]=='}') + (str[y]=='{');
}int solve(int x, int y){if(x>y)return 0;if(dp[x][y]!=-1)return dp[x][y];int i, tmp=maxn;for(i=x+1; i<y-1; i+=2){if(solve(x, i)+solve(i+1, y)<tmp){tmp=solve(x, i)+solve(i+1, y);}}if(match(x, y)+solve(x+1, y-1)<tmp){tmp=match(x, y)+solve(x+1, y-1);}dp[x][y]=tmp;return tmp;
}int main(){int cas=1;while(scanf("%s", str)&&str[0]!='-'){memset(dp, -1, sizeof(dp));len=strlen(str);printf("%d. %d\n", cas++, solve(0, len-1));}return 0;
}
下面是贪心的AC代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=2005;
char str[maxn];int main(){int cas=1;while(scanf("%s", str)&&str[0]!='-'){int i, ans=0, lef=0;for(i=0; str[i]!='\0'; i++){if(str[i]=='{'){lef++;}else if(lef>0){lef--;}else {ans++;lef++;}}printf("%d. %d\n", cas++, ans+lef/2);}return 0;
}
这篇关于hdu 3351 Seinfeld / poj 3991 括号匹配2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
