Algoogle

Algorithm for Programming Contest

PKU 3267 The Cow Lexicon

Category: PKU Tag: dp

The Cow Lexicon

問題概要


辞書と文字列が与えられて, 文字列から最小何文字取り除けば辞書にある単語を繋げた文字列になるか.

解法


dp[i] := i 文字目までで取り除く最小数
文字列の i 番目について, そこから辞書の j 番目の単語を始めるとき何文字取り除くことになるかを考える.
取り除く個数は順に見て合わせていけばいい.

コード


(3267.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
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

const int inf = int(1e9);
int W, L;
string word;
string dict[610];
int dp[512];

int cost(int head, int j){
    for(int tail = 0, i = head; i < L && tail < dict[j].size(); i++){
        if(word[i] == dict[j][tail]) tail++;
        if(tail == dict[j].size()) return i+1 - head - dict[j].size();
    }
    return inf;
}

int main(){
    cin >> W >> L;
    cin >> word;
    for(int i = 0; i < W; i++) cin >> dict[i];

    for(int i = 0; i < 512; i++) dp[i] = inf;
    dp[0] = 0;

    for(int i = 0; i < L; i++){
        for(int j = 0; j < W; j++)
            if(i + dict[j].size() <= L){
            int c = cost(i, j);
            if(c > L) continue;
            int t = i + c + dict[j].size();
            dp[t] = min(dp[t], dp[i]+c);
        }
    }

    int ans = inf;
    for(int i = 0; i <= L; i++)
        ans = min(ans, L-i+dp[i]);

    cout << ans << endl;
    return 0;
}

Comments