Algoogle

Algorithm for Programming Contest

AOJ 2630 Dictionary

Category: AOJ Tag: dp

Dictionary

問題概要


n(<=50)個の文字列が辞書順に並んでいる.
しかし文字列の一部分が読めない.
元の文字列として考えられるのは何通りか.

解法


メモ化再帰します.
dp[l][r][p][c] := 文字列[l,r)のp文字目がc以上の場合の数
とすればあとは以下のように計算する.

区間[l,r)を位置i([l,r])で2つに分割する.
区間[l,i)の位置pがcの場合の数と後半の区間[i,r)の位置pがc+1以上の場合の数の積をdp[l][r][p][c]に加える.
ただし,もとの文字列からありえない場合は計算しない

コード


(2630.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 = 1e9+7;
const char base = 'a'-1;

inline int add(int &x, int y) { return x=(x+y)%mod;}
inline int mul(int x, int y) { return 1LL*x*y%mod;}

int n, dp[64][64][32][32];
char s[64][32];

int solve(int l, int r, int a, int b)
{
        int &ret = dp[l][r][a][b];
        if(~ret) return ret;
        if(l >= r) return ret = 1;

        ret = 0;
        if(b == 27) return ret;
        if(a == 20) return ret = r-l==1;

        for (int i = l; i <= r; i++) {
                if(i != l and ((s[i-1][a] != base+b and s[i-1][a] != '?') or
                               (s[i-1][a] == '?' and b == 0))) break;
                add(ret, mul(solve(l,i,a+1,0), solve(i,r,a,b+1)));
        }
        return ret;
}

void input()
{
        memset(dp,-1,sizeof(dp));
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
                scanf("%s", s[i]);
                for (int j = strlen(s[i]); j < 20; j++) s[i][j] = base;
        }
}

int main()
{
        input();
        printf("%d\n", solve(0,n,0,0));
        return 0;
}

Comments