uva3942 字典树加dp

dp字典树

;s[300005];int sz;const int maxnode = 4000*100+100;int ch[maxnode][26];int val[maxnode];int dp[300005];void insert(char *s){int n = strlen(s);int u = 0;for(int i = 0;i < n;i++){int c = id(s[i]);if(!ch[u][c]){val[sz] = 0;memset(ch[sz],0,sizeof(ch[sz]));ch[u][c] = sz ++;}u = ch[u][c];}val[u] = 1;}int query(int loc,int c){int u = 0;int n = loc + c;for(int i = loc;i <= n;i++){int c = id(s[i]);if(!ch[u][c]){return false;}u = ch[u][c];}return val[u];}int main(){int cc = 1;while(scanf(“%s”,s)!=EOF){int t;int len = strlen(s);memset(ch[0],0,sizeof(ch[0]));memset(dp,0,sizeof(dp));sz = 1;scanf(“%d”,&t);char a[200];while(t–){scanf(“%s”,a);insert(a);}dp[len] = 1;for(int i= len-1;i >=0 ;i–){for(int j = 0;j < 100 && j+i < len;j++){if(query(i,j)){dp[i] += dp[i+j+1];dp[i] %= 20071027;}}}printf(“Case %d: %d\n”,cc++,dp[0]);}return 0;}

开始的时候采用记忆化搜索超时了，，换成dp就可以过了，dp就是非递归的记忆化搜索！

上一篇hdu1251 字典树

顶0踩0

微笑拥抱每一天，做像向日葵般温暖的女子。

相关文章：

你感兴趣的文章：

标签云：