Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <cstdlib>
- #include <cstdarg>
- #include <cassert>
- #include <cstring>
- #include <cstdio>
- #include <vector>
- #include <string>
- #include <queue>
- #include <set>
- #include <map>
- using namespace std;
- typedef unsigned char uchar;
- const int maxn = 104;
- const uchar inf = 104;
- const uchar nan = 255;
- int next[maxn * maxn][26];
- int term[maxn * maxn];
- int size;
- uchar dp[maxn][maxn][maxn * maxn];
- char str[maxn];
- char ss[maxn];
- uchar f(int v, int l, int r) {
- if (v == -1) return inf;
- uchar &res = dp[l][r][v];
- if (res != nan) return res;
- res = inf;
- if (term[v]) {
- if (l + 1 == r) return res = 1;
- res = min((uchar)(f(next[0][str[l + 1] - 'a'], l + 1, r) + 1), res);
- }
- for (int i = l + 1; i < r; i++) {
- uchar add1 = (i == l + 1) ? 0 : f(next[0][str[l + 1] - 'a'], l + 1, i);
- uchar add2 = f(next[v][str[i] - 'a'], i, r);
- res = min(res, (uchar)(add1 + add2));
- }
- return res;
- }
- int main(){
- memset(next, -1, sizeof next);
- scanf("%s", str);
- size = 1;
- int n;
- scanf("%d", &n);
- for (int i = 0; i < n; i++) {
- scanf("%s", ss);
- int p = 0;
- for (int j = 0; ss[j]; j++) {
- if (next[p][ss[j] - 'a'] == -1) {
- next[p][ss[j] - 'a']= size++;
- }
- p = next[p][ss[j] - 'a'];
- }
- term[p] = 1;
- }
- n = strlen(str);
- memset(dp, nan, sizeof dp);
- for (int i = 0; i < n; i++) {
- for (int j = i + 1; j < n; j++) {
- f(next[0][str[i] - 'a'], i, j);
- }
- }
- printf("%d\n", (int)f(next[0][str[0] - 'a'], 0, n));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment