Algoogle

Algorithm for Programming Contest

JOI 春合宿 2011 Deciphering

Category: JOI Tag: dp

Deciphering

問題概要


長さNの文字列とM個の禁止ルール(連続してはいけない2文字)が与えられる.
その文字列から任意個の文字消して長さ1以上の禁止ルールを含まない文字列を得るとき, 得られる何通りあるか.

解法


削除するのではなく頭から順に文字を加えるかどうかでDPする.
dp[i][j] := 入力文字列のi文字目までで文字jが最後に来る場合の数
とすれば更新は文字jに現在の文字cを加えるかどうかでできる(禁止ルールに反するなら加えない).
空文字列に加える場合もある(得られる文字列がそこから始まる場合)
加えないならdp[i+1][j] = dp[i][j]
加えるならdp[i+1][c] += dp[i][j]
ただしj=cのときは加えない場合を無視する(空文字列に加える場合と他の文字に加える場合に完全に包含されるため)

コード


(deciphering.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
const int mod = 10000000;
inline void add(int &a, int b){ a=(a+b)%mod;}

int n, m, fb[32][32], seq[1<<19], dp[2][32];

int solve()
{
        dp[0][26] = 1;
        for (int i = 0; i < n; i++) {
                dp[1][seq[i]] = 0;
                for (int j = 0; j < 27; j++) {
                        if(seq[i] != j) dp[1][j] = dp[0][j];
                        if(!fb[j][seq[i]]) add(dp[1][seq[i]], dp[0][j]);
                }
                swap(dp[0], dp[1]);
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) add(ans, dp[0][i]);
        return ans;
}

void input()
{
        cin >> n;
        char c, d;
        for (int i = 0; i < n; i++) {
                cin >> c;
                seq[i] = c-'A';
        }
        cin >> m;
        for (int i = 0; i < m; i++) {
                cin >> c >> d;
                fb[c-'A'][d-'A'] = 1;
        }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments