AC自动机+状态压缩DP, 由于时限卡的比较死,进制高低位的选择不同可能会导致TLE(o(╯□╰)o),详细见注释
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <queue> #include <algorithm> #include <vector> #include <cstring> #include <stack> #include <cctype> #include <utility> #include <map> #include <string> #include <climits> #include <set> #include <string> #include <sstream> #include <utility> #include <ctime> using std::priority_queue; using std::vector; using std::swap; using std::stack; using std::sort; using std::max; using std::min; using std::pair; using std::map; using std::string; using std::cin; using std::cout; using std::set; using std::queue; using std::string; using std::istringstream; using std::make_pair; using std::getline; using std::greater; using std::endl; using std::multimap; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PAIR; typedef multimap<int, int> MMAP; const int MAXN(510); const int SIGMA_SIZE(4); const int MAXM(110); const int MAXE(4000010); const int MAXH(18); const int INFI((INT_MAX-1) >> 2); const int MOD(20090717); const ULL LIM(1000000000000000ull); int mp[128]; struct AC { int ch[MAXN][SIGMA_SIZE]; int val[MAXN], f[MAXN]; int size; void init() { memset(ch[0], 0, sizeof(ch[0])); f[0] = val[0] = 0; size = 1; } inline int idx(char temp) { return mp[temp]; } void insert(char *S) { int u = 0, id; for(; *S; ++S) { id = idx(*S); if(!ch[u][id]) { memset(ch[size], 0, sizeof(ch[size])); val[size] = 0; ch[u][id] = size++; } u = ch[u][id]; } val[u] += 1; } int que[MAXN]; int front, back; void construct() { front = back = 0; int cur, u; for(int i = 0; i < SIGMA_SIZE; ++i) { u = ch[0][i]; if(u) { que[back++] = u; f[u] = 0; } } while(front < back) { cur = que[front++]; for(int i = 0; i < SIGMA_SIZE; ++i) { u = ch[cur][i]; if(u) { que[back++] = u; f[u] = ch[f[cur]][i]; val[u] += val[f[u]]; } else ch[cur][i] = ch[f[cur]][i]; } } } }; AC ac; int BASE[4]; int quant[4]; inline int encode() { return quant[0]*BASE[0]+quant[1]*BASE[1]+quant[2]*BASE[2]+quant[3]*BASE[3]; } bool vis[MAXN][15010]; int table[MAXN][15010]; int code; //注意每个状态编码可以通过减法递推得到,不要重新计算 int dfs(int u) { if(vis[u][code]) return table[u][code]; int &cur = table[u][code]; cur = 0; int ts, temp; for(int i = 0; i < SIGMA_SIZE; ++i) if(quant[i]) { --quant[i]; code -= BASE[i]; ts = ac.ch[u][i]; temp = dfs(ts)+ac.val[ts]; cur = temp > cur? temp: cur; code += BASE[i]; ++quant[i]; } vis[u][code] = true; return cur; } void solve() { memset(vis, 0, sizeof(vis[0])*ac.size); code = encode(); dfs(0); printf("%d\n", table[0][code]); } char str[60]; int main() { mp['A'] = 0; mp['C'] = 1; mp['G'] = 2; mp['T'] = 3; int n, n_case(0); while(scanf("%d", &n), n) { ac.init(); for(int i = 0; i < n; ++i) { scanf("%s", str); ac.insert(str); } ac.construct(); scanf("%s", str); quant[0] = quant[1] = quant[2] = quant[3] = 0; for(char *pi = str; *pi; ++pi) ++quant[mp[*pi]]; BASE[3] = 1; //如果把'A'作为低位的话就会TLE,还要注意注意每个位的的状态数为quant+1 BASE[2] = quant[3]+1; BASE[1] = (quant[2]+1)*BASE[2]; BASE[0] = (quant[1]+1)*BASE[1]; printf("Case %d: ", ++n_case); solve(); } return 0; }