湖南师范大学2018年大学生程序设计竞赛新生赛 I 巨巨的提问

链接：https://www.nowcoder.com/acm/contest/127/I
来源：牛客网
文章转载自：xuanqis.com

题目描述

盼成巨巨是511的学神！
    有一天，宇鑫大佬在玩硬币，将硬币摆成一排，巨巨走过来看了一眼，向宇鑫大佬提出问题：“假如显示出正面的硬币为’(‘，反面的硬币为‘)’我可以将一段区间的括号同时翻转（‘(’<---->‘)’），至少需要多少次区间翻转将其变为合法的括号序列？”
面对巨巨的提问，宇鑫有点无助，请您帮帮他至少需要多少次。
合法括号序列是这样递归定义的：
1.()是合法括号序列；

2.如果A是合法的，那么(A)也是合法的；

3.如果A和B都合法，那么AB合法。

输入描述:

第1行：输入一个偶数n(2≤n≤2000)表示序列长度。

第2行：输入长度为n的括号字符串。

输出描述:

输出1行：需要翻转的最少次数。
示例1

输入

6
()))))

输出

1

说明

下标从1开始，翻转区间[3,4]，就变成了()(())，翻转1次就合法了！

思路

使用dp[i][j][0]来记录第i个字符不翻转时未匹配的左括号为j时的最小翻转次数；dp[i][j][1]来记录第i个字符翻转时未匹配的左括号为j时的最小翻转次数。最后dp[n][0][1]和dp[n][0][0]的小的那个就是答案。

代码

#include<bits/stdc++.h>

using namespace std;  

int dp[2001][2001][2];   
char str[2001];  
int main(){
    //freopen("1.txt", "r", stdin);  
    int n;  
    scanf("%d", &n);  
    scanf("%s",str+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(str[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]));  //输出小的那个
}