首页 > ACM题库 > HDU-杭电 > HDU 2825-Wireless Password-动态规划-[解题报告]HOJ
2014
02-17

HDU 2825-Wireless Password-动态规划-[解题报告]HOJ

Wireless Password

问题描述 :

Liyuan lives in a old apartment. One day, he suddenly found that there was a wireless network in the building. Liyuan did not know the password of the network, but he got some important information from his neighbor. He knew the password consists only of lowercase letters ‘a’-'z’, and he knew the length of the password. Furthermore, he got a magic word set, and his neighbor told him that the password included at least k words of the magic word set (the k words in the password possibly overlapping).

For instance, say that you know that the password is 3 characters long, and the magic word set includes ‘she’ and ‘he’. Then the possible password is only ‘she’.

Liyuan wants to know whether the information is enough to reduce the number of possible passwords. To answer this, please help him write a program that determines the number of possible passwords.

输入:

There will be several data sets. Each data set will begin with a line with three integers n m k. n is the length of the password (1<=n<=25), m is the number of the words in the magic word set(0<=m<=10), and the number k denotes that the password included at least k words of the magic set. This is followed by m lines, each containing a word of the magic set, each word consists of between 1 and 10 lowercase letters ‘a’-'z’. End of input will be marked by a line with n=0 m=0 k=0, which should not be processed.

输出:

There will be several data sets. Each data set will begin with a line with three integers n m k. n is the length of the password (1<=n<=25), m is the number of the words in the magic word set(0<=m<=10), and the number k denotes that the password included at least k words of the magic set. This is followed by m lines, each containing a word of the magic set, each word consists of between 1 and 10 lowercase letters ‘a’-'z’. End of input will be marked by a line with n=0 m=0 k=0, which should not be processed.

样例输入:

10 2 2
hello 
world 
4 1 1
icpc 
10 0 0
0 0 0

样例输出:

2
1
14195065

Wireless Password

题意:给m个串(m<=10),求长度为n且至少含k个可重叠给定串的串的数目。AC自动机+状压dp,i为串长,j为二进制状态,表示当前包含哪些串,k为trie树上一节点编号。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

#define mod 20090717
#define pb push_back
#define lowbit(x) ((x)&(-x))
struct node{
    int son[26],fail;
    int cnt;//二进制状态,标记包括自己和前面,有哪些给定字串
    node(){memset(son,0,sizeof(son));fail=0;cnt=0;}
};
vector<node> ac;
int hash[256];
int dp[30][1<<11][110];
int n,m,K;
int map[1<<11];//预处理出二进制数中1的个数

void init() {
    memset(map,0,sizeof(map));
    for(int i=0;i<(1<<10);++i) {
        map[i]=map[i>>1]+(i&1);
    }
    for(int i=0;i<26;++i) hash['a'+i]=i;
}

void insert(const char *str,int num) {
    int p=0,i=0;
    while(str[p]) {
        if(!ac[i].son[hash[str[p]]]) {
            ac[i].son[hash[str[p]]]=ac.size();
            ac.pb(node());
        }
        i=ac[i].son[hash[str[p]]];
        ++p;
    }
    ac[i].cnt=1<<num;
}

void getFail() {
    queue<int> qu;
    qu.push(0);
    while(!qu.empty()) {
        int cur=qu.front();qu.pop();
        for(int i=0;i<26;++i) {
            int nex=ac[cur].son[i];
            int p=ac[cur].fail;
//            while(~p&&!ac[p].son[i]) p=ac[p].son[i];//这部没必要,浅层节点必有儿子
            if(nex) {
                qu.push(nex);
                if(~p) ac[nex].fail=ac[p].son[i],ac[nex].cnt|=ac[ac[p].son[i]].cnt;
                else ac[nex].fail=0;
            }
            else {
                if(~p) ac[cur].son[i]=ac[p].son[i];//空儿子不是指向根,就是指向实儿子
            }
        }

    }
}

int main() {
    ios::sync_with_stdio(false);
    init();
    while(cin >> n >> m >> K,n||m||K) {
        ac.clear();
        ac.pb(node());
        ac[0].fail=-1;
        for(int i=0;i<m;++i) {
            char str[20];
            cin >> str;
            insert(str,i);
        }
        getFail();
//        memset(dp,0,sizeof(dp));//dp数组太大,全部清0太耗时
        for(int i=0;i<=n;++i)
            for(int j=0;j<(1<<m);++j)
                for(int k=0;k<ac.size();++k)
                    dp[i][j][k]=0;
        dp[0][0][0]=1;
        int ans=0;
        for(int i=0;i<n;++i)
            for(int j=0;j<(1<<m);++j)
                for(int k=0;k<ac.size();++k) {
                    if(!dp[i][j][k]) continue;
                    for(int p=0;p<26;++p) {
                        int spos=ac[k].son[p],sta=j|ac[spos].cnt;
                        dp[i+1][sta][spos]+=dp[i][j][k];
                        dp[i+1][sta][spos]%=mod;
                    }
                }
        for(int i=0;i<(1<<m);++i)
            for(int j=0;j<ac.size();++j)
                if(map[i]>=K) {ans+=dp[n][i][j];ans%=mod;}//这里不要忘记取模
        cout << ans << endl;
    }
    return 0;
}

解题参考:http://blog.csdn.net/qwe20060514/article/details/8045850