UVALive - 3942 Remember the Word （Trie + DP）

题意：

给定一篇长度为L的小写字母文章，然后给定n个字母，问有多少种方法用这些字母组成文章。

思路：

用dp[i]来表达[i , L]的方法数，那么dp[i] 就可以从dp[len(x) + i]转移过来，注意dp[L+1]要初始化为1.

递推写法

#include <bits/stdc++.h>

using namespace std;

const int maxN = 3e5 + ;

const int mod =  ;

char in[maxN];

int n;

struct Trie {

    int ch[maxN][];

    int val[maxN];

    int sz;

    void Init(){sz = ; memset(ch[], , sizeof(ch[])); memset(val, , sizeof(val));}

    int idx(char c) {return c - 'a';}

    void Insert(char *s){

        int u = , n = strlen(s);

        for(int i = ; i < n; i++){

            int c = idx(s[i]);

            if(!ch[u][c]){

                memset(ch[sz], , sizeof(ch[sz]));

                val[sz] = ;

                ch[u][c] = sz++;

            }

            u = ch[u][c];

        }

        val[u] = n;

    }

}tree;

long long dp[maxN];

int main(){

//    freopen("1.txt","r", stdin);

    int kase = ;

    while(~scanf("%s", in)){

        tree.Init();

        memset(dp ,  , sizeof(dp));

        scanf("%d", &n);

        char word[];

        for(int i = ; i < n; i++){

            scanf("%s", word);

            tree.Insert(word);

        }

        int len = strlen(in);

        dp[len] = ;

        for(int pos = len ; pos >= ; pos--){

            int u = ;

            for(int i = pos, wordLen = ; i < len; i++, wordLen++){

                int c = tree.idx(in[i]);

                if(tree.ch[u][c] == ) break;

                u = tree.ch[u][c];

                if(tree.val[u] != ){

                    dp[pos] += dp[pos + wordLen];

                    dp[pos] %= mod;

                }

            }

        }

        printf("Case %d: %lld\n", kase++, dp[]);

    }

    return ;

}

记忆化搜索

#include <bits/stdc++.h>

using namespace std;

const int maxN = 2e6 + ;

const int mod =  ;

char in[maxN];

int n;

struct Trie {

    int ch[maxN][];

    int val[maxN];

    int sz;

    void Init(){

        sz = ;

        memset(ch[], , sizeof(ch[]));

        memset(val, , sizeof(val));

    }

    int idx(char c) {return c - 'a';}

    void Insert(char *s){

        int u = , n = strlen(s);

        for(int i = ; i < n; i++){

            int c = idx(s[i]);

            if(!ch[u][c]){

                memset(ch[sz], , sizeof(ch[sz]));

                val[sz] = ;

                ch[u][c] = sz++;

            }

            u = ch[u][c];

        }

        val[u] = n;

    }

}tree;

long long dp[maxN];

int dfs(int pos){

    int temp = pos;

    if(dp[pos] > ) return dp[pos];

    int ret = ;

    int adr = ;

    while(tree.ch[adr][in[pos] - 'a']){

        adr = tree.ch[adr][in[pos] - 'a'];

        if(tree.val[adr] != ){

            ret = (ret + dfs(pos + )) % mod;

        }

        pos ++;

    }

    dp[temp] = ret;

    return ret;

}

int main(){

    freopen("1.txt","r", stdin);

    int ncase = ;

    while(~scanf("%s", in)){

        tree.Init();

        scanf("%d", &n);

        char word[];

        for(int i = ; i < n; i++){

            scanf("%s", word);

            tree.Insert(word);

        }

        int l = strlen(in);

        for(int i = ;i <= l; i ++)dp[i] = ;

        dp[l] = ;

        printf("Case %d: %d\n",ncase ++ , dfs());

    }

    return ;

}

巴特西

UVALive - 3942 Remember the Word （Trie + DP）

题意：

思路：

最新文章

热门文章