首页 > 代码库 > HNU 13108 Just Another Knapsack Problem ac自动机上的dp

HNU 13108 Just Another Knapsack Problem ac自动机上的dp

给定一个母串。

给出n个子串和子串对应的价值

用下面的n个子串拼出母串,则得到的价值为子串价值和

拼接时不能有重叠遗漏(即母串的每个位置恰好被覆盖一次)

在ac自动机上找的时候搞一个dp数组就好了


[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
    1. #include<stdio.h>  
    2. #include<iostream>  
    3. #include<cmath>  
    4. #include<cstring>  
    5. #include<queue>  
    6. using namespace std;  
    7.   
    8. const int maxnode = 250*1000+10000;  
    9. const int sigma_size = 26;  
    10.   
    11. struct Trie{  
    12.     int dp[101000];  
    13.     int ch[maxnode][sigma_size];  
    14.     int val[maxnode];    //该单词在模式串中出现的最大价值  
    15.     int last[maxnode];  
    16.     int f[maxnode];      //失配数组  
    17.     int pre[maxnode];    //该单词的前驱  
    18.     int len[maxnode];    //以该单词结尾的单词长度  
    19.     int Char[maxnode];   //该单词对应的字母  
    20.     int road[maxnode];   //路径压缩优化 针对计算模式串出现的种数  
    21.     int sz;  
    22.     int Newnode()  
    23.     {  
    24.         val[sz] = f[sz] = last[sz] = len[sz] = 0;  
    25.         memset(ch[sz], 0, sizeof ch[sz]);  
    26.         return sz++;  
    27.     }  
    28.     void init(){  
    29.         sz=0;  
    30.         Newnode();  
    31.     }  
    32.     int idx(char c){ return c-‘a‘; }  
    33.     int insert(char *s, int v){  
    34.         int u = 0;  
    35.         for(int i = 0, c; s[i] ;i++){  
    36.             c = idx(s[i]);  
    37.             if(!ch[u][c])  
    38.                 ch[u][c] = Newnode();  
    39.             pre[ch[u][c]] = u;  
    40.             Char[ch[u][c]] = s[i];  
    41.             len[ch[u][c]] = len[u]+1;  
    42.             u = ch[u][c];  
    43.         }  
    44.         val[u] = max(val[u], v);  
    45.         return u;  
    46.     }  
    47.    void getFail(){  
    48.         queue<int> q;  
    49.         for(int i = 0; i<sigma_size; i++)  
    50.             if(ch[0][i]) q.push(ch[0][i]);  
    51.         int r, c, u, v;  
    52.         while(!q.empty()){  
    53.             r = q.front(); q.pop();  
    54.             for(c = 0; c<sigma_size; c++){  
    55.                 u = ch[r][c];  
    56.                 if(!u)continue;  
    57.                 q.push(u);  
    58.                 v = f[r];  
    59.                 while(v && ch[v][c] == 0) v = f[v]; //沿失配边走上去 如果失配后有节点 且 其子节点c存在则结束循环  
    60.                 f[u] = ch[v][c];  
    61.             }  
    62.         }  
    63.     }  
    64.     void find(char *T){  
    65.         int j = 0;  
    66.         for(int i = 0, c, temp; T[i] ; i++){  
    67.             dp[i] = 0;  
    68.             c = idx(T[i]);  
    69.             while(j && ch[j][c]==0) j = f[j];  
    70.             j = ch[j][c];  
    71.   
    72.             temp = j;  
    73.             while(temp){  
    74.                 if(val[temp]){  
    75.                     if(i-len[temp] < 0)  
    76.                         dp[i] = max(dp[i], val[temp]);  
    77.                     else if(dp[i-len[temp]])  
    78.                     dp[i] = max(dp[i], dp[i-len[temp]]+val[temp]);  
    79.                 }  
    80.                 temp = f[temp];  
    81.             }  
    82.        //     puts("");  
    83.         }  
    84.     }  
    85. }ac;  
    86. char s[100100], t[350];  
    87. void input(){  
    88.     int n, val; cin>>n;  
    89.     ac.init();  
    90.     while(n--){  
    91.         scanf("%s %d", t, &val);  
    92.         ac.insert(t, val);  
    93.     }  
    94. }  
    95. int main(){  
    96.     while(~scanf("%s", s)){  
    97.         input();  
    98.         ac.getFail();  
    99.         ac.find(s);  
    100.         printf("%d\n", ac.dp[strlen(s)-1]);  
    101.     }  
    102.     return 0;  

HNU 13108 Just Another Knapsack Problem ac自动机上的dp