SRM664 Div1 Easy BearCries

2015/10/15 (Thu) SRM DP

問題

問題文

; と _ だけが含まれる文字列が与えられる．これを ;_____; のように 1 つ以上の _ が ; で挟まれるような文字列に分ける．全ての文字が分解後のどれか 1 つの文字列に含まれていないといけない． 分け方は何通り？

方針

_ を口，; を目ということにする． $dp(i,j,k) = [0,i)$ の区間で口が付いていない左目の数が $j$ 個で， 口が 1 つ以上付いて右目がついていない左目の数が $k$ 個あるように分けるパターンの数とおく． 例えば ;_ は左目の右に口がくっつくかくっつかないかで 2 つの見方があり，それぞれ $dp(2,0,1)$ と $dp(2,1,0)$ に計上される． このようにおくと答えは $dp(n,0,0)$ になる． 漸化式はコメントを読んでください．

実装

class BearCries {
public:
    string s;
    int n;
    int solve(){
        static mint dp[222][222][222];
        memset(dp,0,sizeof(dp));
        dp[0][0][0] = 1;
        rep(i,n)rep(j,n)rep(k,n){
            const mint & cur = dp[i][j][k];
            if(cur.x == 0) continue;
            if(s[i] == ';'){
                // ; を k 個ある ;__... のどれかの左目にする
                if(k > 0) dp[i+1][j][k-1] += cur*k;
                // ; をどの ;__... にもくっつけずに右目にする
                dp[i+1][j+1][k] += cur;
            } else {
                // _ を j 個ある ; のどれかの口にする
                if(j > 0) dp[i+1][j-1][k+1] += cur*j;
                // _ を k 個ある ;__... のどれかの口にさらに繋げる
                dp[i+1][j][k] += cur*k;
            }
        }
        return dp[n][0][0].x;
    }
    int count(string message) {
        s = message;
        n = s.size();
        return solve();
    }
};