hdu 2825 Wireless Password
AC自动机+DP。第一道自己做出来的AC+DP。。自动机部分相信大家已经很熟悉了,DP那部分其实就是在自动机上跑出一个新串即可,用val数组标记自动机中到达每个节点所包含的单词种类(用状态压缩)。因为范围很小,所以直接暴力dp就可以了,注意用滚动数组实现DP,不然会超时。。#include <algorithm> #include <iostream> #include <sstream> #include <cstdlib> #include <climits> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <cctype> #include <queue> #include <cmath> #include <set> #include <map> #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; }
补充:软件开发 , C++ ,