题解：P7248 [BalticOI 2012] 括号 (Day1)

· · 题解

P7248 [BalticOI 2012] 括号 (Day1) 题解：

题意非常好理解，相信大家都能看懂，这里不再赘述，直接说思路。

1.思路：

题目中规定只能用 ( 来替换 [ 和 ] ，所以，当给定的不合法的字符串中左括号 ( 的数量小于右括号 ) 的数量时，显然没有能转化为它的合法字符串。

所以，下面只讨论左括号数量大于右括号数量的字符串。

举个例子：

对于 ()(( 这个不合法的字符串来说：它只能由 ()[] 转换而来。

但如果我们将这个合法的字符串中的所有 [ 转换为 ( ，] 转换为 ) 就可以得到一个只包含圆括号的合法字符串： ()() 。

于是题目中的问题就转换为了将原字符串中的不匹配的左括号匹配起来的方案数。显然用动态规划求解。

设 dp_{i,j} 为第 i 个位置还有 j 个未匹配的 ( 时的方案数，则有：

$dp_{i,j}=dp_{i-1,j-1}+dp_{i-1,j+1}$（此字符为`(`）

由于内存限制，使用滚动数组。

该说的都说完了，上代码：

2.Code：

码风很烂，将就着看。 

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
const int MOD = 1000000009;
int n;
char ch;
int dp[3][MAXN];

int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    dp[0][0]=1;
    for(register int i=1;i<=n;i++){
        cin>>ch;
        for(register int j=0;j<=min(i,n-i);j++){
            if (!j || ch == ')') dp[i & 1][j] = dp[(i+1)&1][j + 1];
            else dp[i & 1][j] = (dp[(i+1)&1][j + 1] + dp[(i+1)&1][j - 1]) % MOD;
        }
    }
    cout << dp[n & 1][0] << '\n';
    return 0;
}

全文完。 点个赞呗！！！