nikolaj

Untitled

Feb 25th, 2013
215
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <cstdarg>
  5. #include <cassert>
  6. #include <cstring>
  7. #include <cstdio>
  8. #include <vector>
  9. #include <string>
  10. #include <queue>
  11. #include <set>
  12. #include <map>
  13.  
  14. using namespace std;
  15.  
  16. typedef unsigned char uchar;
  17.  
  18. const int maxn = 104;
  19. const uchar inf = 104;
  20. const uchar nan  = 255;
  21.  
  22. int next[maxn * maxn][26];
  23. int term[maxn * maxn];
  24. int size;
  25. uchar dp[maxn][maxn][maxn * maxn];
  26. char str[maxn];
  27. char ss[maxn];
  28.  
  29.  
  30. uchar f(int v, int l, int r) {
  31.     if (v == -1) return inf;
  32.     uchar &res = dp[l][r][v];
  33.     if (res != nan) return res;
  34.     res = inf;
  35.     if (term[v]) { 
  36.         if (l + 1 == r) return res = 1;
  37.         res = min((uchar)(f(next[0][str[l + 1] - 'a'], l + 1, r) + 1), res);
  38.     }
  39.     for (int i = l + 1; i < r; i++) {
  40.         uchar add1 = (i == l + 1) ? 0 : f(next[0][str[l + 1] - 'a'], l + 1, i);
  41.         uchar add2 = f(next[v][str[i] - 'a'], i, r);
  42.         res = min(res, (uchar)(add1 + add2));
  43.     }
  44.     return res;
  45. }
  46.  
  47.                                
  48.  
  49. int main(){
  50.     memset(next, -1, sizeof next);
  51.     scanf("%s", str);
  52.     size = 1;
  53.     int n;
  54.     scanf("%d", &n);
  55.     for (int i = 0; i < n; i++) {
  56.         scanf("%s", ss);
  57.         int p = 0;
  58.         for (int j = 0; ss[j]; j++) {
  59.             if (next[p][ss[j] - 'a'] == -1) {
  60.                 next[p][ss[j] - 'a']= size++;
  61.             }
  62.             p = next[p][ss[j] - 'a'];
  63.         }
  64.         term[p] = 1;
  65.     }                          
  66.     n = strlen(str);
  67.     memset(dp, nan, sizeof dp);
  68.     for (int i = 0; i < n; i++) {
  69.         for (int j = i + 1; j < n; j++) {
  70.             f(next[0][str[i] - 'a'], i, j);
  71.         }
  72.     }
  73.     printf("%d\n", (int)f(next[0][str[0] - 'a'], 0, n));
  74.     return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment