Hatena::Grouptopcoder

yambe2002の日記

 | 

2016-03-29

SRM686 Div2 Hard: BracketSequenceDiv2

00:24

解法はこちらを参考にさせていただいた。

http://pekempey.hatenablog.com/entry/2016/03/29/174037


左カッコと右カッコからなる文字列が与えられる。

任意の文字を削除したとき、正しいカッコ列は何通り作れるか。


DP[できた文字列の最後文字がある位置][開いているカッコの数] を設定する。

すると、DP[i][j]について

 DP[次の左カッコ位置][j+1] ← DP[i][j]を足す

 DP[次の右カッコ位置][j-1] ← DP[i][j]を足す

が成り立つ。

開いているカッコ数がゼロの部分を合計すれば答えになる。

public class BracketSequenceDiv2 {
    const int MOD = 1000000007;

    public int count(string s) {
        var dp = new int[s.Length, s.Length + 2];

        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == '(')
            {
                dp[i, 1] = 1;
                break;  //dont forget this!!
            }
        }

        for (int i = 0; i < s.Length; i++)
        {
            for (int j = 0; j < s.Length + 1; j++)
            {
                var nextLeftBracket = s.IndexOf('(', i + 1);
                var nextRightBracket = s.IndexOf(')', i + 1);

                if (nextLeftBracket != -1) dp[nextLeftBracket, j + 1] = (dp[nextLeftBracket, j + 1] + dp[i, j]) % MOD;
                if (nextRightBracket != -1 && j - 1 >= 0)
                {
                    dp[nextRightBracket, j - 1] = (dp[nextRightBracket, j - 1] + dp[i, j]) % MOD;
                }
            }
        }

        long ret = 0;
        for (int i = 0; i < s.Length; i++)
        {
            ret += dp[i, 0];
            ret %= MOD;
        }
        return (int)ret;
    }
}
 |