NC16133. 巨巨的提问
描述
1.()是合法括号序列；
2.如果A是合法的，那么(A)也是合法的；
3.如果A和B都合法，那么AB合法。
输入描述
第1行：输入一个偶数n(2≤n≤2000)表示序列长度。
第2行：输入长度为n的括号字符串。
输出描述
输出1行：需要翻转的最少次数。
示例1
输入:
6 ()))))
输出:
1
说明:
下标从1开始，翻转区间[3,4]，就变成了()(())，翻转1次就合法了！C++11(clang++ 3.9) 解法, 执行用时: 29ms, 内存消耗: 31972K, 提交时间: 2020-04-03 22:27:59
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[2005][2005][2];
char s[2005];
int main()
{
int n;
scanf("%d",&n);
scanf("%s",s+1);
memset(dp,0x3f,sizeof(dp));
dp[0][0][0]=0;
for(int i=1;i<=n;i++)
for(int j=i;j>=0;j-=2)
{
if(s[i]=='(')
{
dp[i][j][0]=min(dp[i-1][j-1][0],dp[i-1][j-1][1]);
dp[i][j][1]=min(dp[i-1][j+1][0]+1,dp[i-1][j+1][1]);
}
else
{
dp[i][j][0]=min(dp[i-1][j+1][0],dp[i-1][j+1][1]);
dp[i][j][1]=min(dp[i-1][j-1][0]+1,dp[i-1][j-1][1]);
}
}
cout<<min(dp[n][0][1],dp[n][0][0])<<endl;
return 0;
}
C++14(g++5.4) 解法, 执行用时: 30ms, 内存消耗: 31864K, 提交时间: 2018-06-06 21:08:34
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2002;
int dp[N][N][2];
char s[N];
int main(){
int n;
scanf("%d%s",&n,s+1);
memset(dp,0x3f3f3f3f,sizeof(dp));
dp[0][0][0]=0;
for(int i=1;i<=n;++i) {
for(int j=i;j>=0;j-=2){
if(s[i]=='('){
dp[i][j][1]=min(dp[i-1][j+1][0]+1,dp[i-1][j+1][1]);
dp[i][j][0]=min(dp[i-1][j-1][0],dp[i-1][j-1][1]);
}
else {
dp[i][j][1]=min(dp[i-1][j-1][0]+1,dp[i-1][j-1][1]);
dp[i][j][0]=min(dp[i-1][j+1][0],dp[i-1][j+1][1]);
}
}
}
printf("%d\n",min(dp[n][0][1],dp[n][0][0]));
}