日韩久久久精品,亚洲精品久久久久久久久久久,亚洲欧美一区二区三区国产精品 ,一区二区福利

HDU 2825 Wireless Password(AC自動(dòng)機(jī)+狀壓DP)

系統(tǒng) 1982 0

題意:有一個(gè)長(zhǎng)為n(n<= 25) 的字符串,它至少由k個(gè)magic word 組成,現(xiàn)在給出m個(gè)magic word,求出這個(gè)字符串組成的可能種數(shù)。

構(gòu)造AC自動(dòng)機(jī)進(jìn)行搜索,dp【i】【j】【k】表示字符串長(zhǎng)度為i,匹配字典樹(shù)上的第j個(gè)節(jié)點(diǎn),并且已經(jīng)匹配上k個(gè)magic word時(shí)的總數(shù)。

則轉(zhuǎn)移方程為 (dp【i+1】【j的兒子】【k ?| ?j的兒子的狀態(tài)】 += dp【i】【j】【k】) % mod;

需要注意的是,因?yàn)閱卧~可以重復(fù)使用,所以單詞結(jié)尾的fail 指向root 指向的各節(jié)點(diǎn)


?

    #include <iostream>

#include <algorithm>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <vector>

#include <set>

#include <queue>

#include <stack>

#include <climits>//形如INT_MAX一類的

#define MAX 100005

#define mod 20090717

#define INF 0x7FFFFFFF

#define REP(i,s,t) for(int i=(s);i<=(t);++i)

#define LL long long

#define mem(a,b) memset(a,b,sizeof(a))

#define mp(a,b) make_pair(a,b)

#define L(x) x << 1

#define R(x) x << 1 | 1

# define eps 1e-5

//#pragma comment(linker, "/STACK:36777216") ///傳說(shuō)中的外掛

using namespace std;



struct Trie {

    int next[26] ;

    int fail ;

    int buff ;

    void init() {

        memset(next,0,sizeof(next)) ;

        fail = -1 ;

        buff = 0 ;

    }

} a[111];

int cnt,n,m,K;

int q[111] , dp[30][111][1 << 10];

char keyword[22];



void insert(char *s,int pos) {

    int p = 0 ;

    for(int i = 0 ; s[i] ; i ++) {

        int t = s[i] - 'a' ;

        if(a[p].next[t] == 0) {

            a[cnt].init();

            a[p].next[t] = cnt ++;

        }

        p = a[p].next[t] ;

    }

    a[p].buff = 1 << pos;

}

void ac_bfs() {

    int i,head = 0,tail = 0;

    q[tail ++] = 0;

    while(head < tail) {

        int front = q[head ++];

        for(i = 0; i < 26 ; i ++) {

            if(a[front].next[i] == 0) {

                if(front != 0) a[front].next[i] = a[a[front].fail].next[i];

            } else {

                int p = a[front].fail ;

                while(p != -1) {

                    if(a[p].next[i] != 0) {

                        a[a[front].next[i]].fail = a[p].next[i] ;

                        a[a[front].next[i]].buff |= a[a[p].next[i]].buff;//狀態(tài)合并,因?yàn)槿绻鹒ail指向的節(jié)點(diǎn)也是某個(gè)magic word的結(jié)尾,那么相當(dāng)于一次找到兩個(gè)magic word

                        break ;

                    }

                    p = a[p].fail ;

                }

                if(p == -1) a[a[front].next[i]].fail = 0 ;

                q[tail ++] = a[front].next[i] ;

            }

        }

    }

}



int calone(int x) {

    int cal = 0;

    while(x) {

        if(x & 1) cal ++;

        x = x >> 1;

    }

    return cal;

}



void solve() {

    dp[0][0][0] = 1;

    int total = 1 << m;

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

        for(int j=0; j<cnt; j++) {

            for(int k=0; k<total; k++) {

                if(dp[i][j][k] == 0) continue;

                for(int l=0; l<26; l++) {

                    int buff = a[a[j].next[l]].buff;

                    dp[i+1][a[j].next[l]][k | buff] = (dp[i+1][a[j].next[l]][k | buff] + dp[i][j][k]) % mod;

                }

            }

        }

    }

    int ans = 0;

    for(int j=0; j<cnt; j++) {

        for(int k=0; k<total; k++) {

            if(calone(k) < K) continue;

            ans = (ans + dp[n][j][k] ) % mod;

        }

    }

    printf("%d\n",ans);

}



int main() {

    while(scanf("%d%d%d",&n,&m,&K)) {

        if(n == 0 && m == 0 && K == 0) break;

        a[0].init();

        cnt = 1;

        for(int i=0; i<m; i++) {

            scanf("%s",keyword);

            insert(keyword,i);

        }

        ac_bfs();

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

            for(int j=0; j<cnt; j++) {

                for(int l=0; l<(1<<m); l++) {

                    dp[i][j][l] = 0;

                }

            }

        }

        solve();

    }

    return 0;

}


  


?

現(xiàn)在缺少dp的思路和靈感.......照著別人的思路敲的.....有些地方依舊有待解決

?

HDU 2825 Wireless Password(AC自動(dòng)機(jī)+狀壓DP)


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號(hào)聯(lián)系: 360901061

您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對(duì)您有幫助就好】

您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長(zhǎng)會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 闽侯县| 富源县| 太谷县| 哈巴河县| 璧山县| 招远市| 库伦旗| 陆河县| 甘孜县| 定结县| 石嘴山市| 昌邑市| 乌鲁木齐县| 虞城县| 公主岭市| 印江| 吴堡县| 黔西县| 利辛县| 隆德县| 泸州市| 二连浩特市| 三明市| 巴马| 阿拉善盟| 临沧市| 南陵县| 苍溪县| 金平| 新余市| 景德镇市| 格尔木市| 家居| 育儿| 水富县| 佛冈县| 甘肃省| 临沧市| 彭泽县| 定结县| 慈利县|