hdu 2825 Wireless Password - c++编程基础

AC自动机+DP。第一道自己做出来的AC+DP。。自动机部分相信大家已经很熟悉了，DP那部分其实就是在自动机上跑出一个新串即可，用val数组标记自动机中到达每个节点所包含的单词种类（用状态压缩）。因为范围很小，所以直接暴力dp就可以了，注意用滚动数组实现DP，不然会超时。。

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#define CLR(a, b) memset(a, b, sizeof(a))  
using namespace std;  
  
const int MAX_NODE = 11 * 11;  
const int INF = 0x3f3f3f3f;  
const int MOD = 20090717;  
const int CHILD_NUM = 26;  
const int N = 30;  
  
class ACAutomaton  
{  
private:  
    int chd[MAX_NODE][CHILD_NUM];  
    int fail[MAX_NODE];  
    int val[MAX_NODE];  
    int Q[MAX_NODE];  
    int ID[128];  
    int sz;  
public:  
    void Initialize()  
    {  
        fail[0] = 0;  
        for(int i = 0; i < 26; i ++)  
            ID[i + 'a'] = i;  
    }  
    void Reset()  
    {  
        CLR(chd[0] , 0);sz = 1;  
        CLR(val, 0);  
    }  
    void Insert(char *a, int sit)  
    {  
        int p = 0;  
        for ( ; *a ; a ++)  
        {  
            int c = ID[*a];  
            if (!chd[p][c])  
            {  
                CLR(chd[sz] , 0);  
                chd[p][c] = sz ++;  
            }  
            p = chd[p][c];  
        }  
        val[p] |= sit;  
    }  
    void Construct()  
    {  
        int *s = Q , *e = Q;  
        for (int i = 0 ; i < CHILD_NUM ; i ++)  
        {  
            if (chd[0][i])  
            {  
                fail[ chd[0][i] ] = 0;  
                *e ++ = chd[0][i];  
            }  
        }  
        while (s != e)  
        {  
            int u = *s++;  
            for (int i = 0 ; i < CHILD_NUM ; i ++)  
            {  
                int &v = chd[u][i];  
                if (v)  
                {  
                    *e ++ = v;  
                    fail[v] = chd[fail[u]][i];  
                    val[v] |= val[fail[v]];  
                }  
                else  
                {  
                    v = chd[fail[u]][i];  
                }  
            }  
        }  
    }  
    int ok(int s)  
    {  
        int ret = 0;  
        while(s)  
        {  
            if(s & 1) ret ++;  
            s >




>= 1;  
        }  
        return ret;  
    }  
    int dp[2][MAX_NODE][1 << 10];  
    int Work(int n, int m, int k)  
    {  
        int ret = 0, T, tmp;  
        CLR(dp, 0);dp[0][0][0] = 1;  
        for(int i = 0; i < n; i ++)  
        {  
            CLR(dp[(i+1)&1], 0);  
            for(int j = 0; j < sz; j ++)  
                for(int v = 0; v < (1 << m); v ++)  
                    if(dp[i & 1][j][v])for(int s = 0; s < 26; s ++)  
                    {  
                        T = chd[j][s];  
                        tmp = v | val[T];  
                        dp[(i+1)&1][T][tmp] += dp[i & 1][j][v];  
                        if(dp[(i+1)&1][T][tmp] >= MOD)  
                            dp[(i+1)&1][T][tmp] -= MOD;  
                    }  
        }  
        for(int i = 0; i < sz; i ++)  
            for(int j = 0; j < (1 << m); j ++)  
                if(ok(j) >= k) ret += dp[n & 1][i][j], ret %= MOD;  
        return ret;  
    }  
} AC;  
  
char ch[N];  
  
int main()  
{  
    //freopen("input.txt", "r", stdin);  
    AC.Initialize();  
    int n, m, k;  
    while (scanf("%d%d%d", &n, &m, &k), n + m + k)  
    {  
        AC.Reset();  
        for (int i = 0 ; i < m ; i ++)  
        {  
            char temp[15];  
            scanf("%s", temp);  
            AC.Insert(temp, 1 << i);  
        }  
        AC.Construct();  
        printf("%d\n", AC.Work(n, m, k));  
    }  
    return 0;  
}