题目链接

题意：给定n个模式串，每个模式串都有权值。文本串如果包含某个模式串，就加上该模式串的权值（如果某个模式串多次出现，只计算一次的贡献），求所有长度为L的文本串中权值最大的是多少。

AC自动机+DP 的入门题。n最大只有10，用二进制状态压缩来表示n个模式串的出现情况。dp[i][j][k] i代表当前文本串长度，j代表当前在AC自动机上第 j个结点，k就是二进制压缩的状态，表示当前n个串的出现情况。DP数组的值为0或1，表示对应的状态是否存在。最后遍历所有二进制压缩的状态，计算其贡献并取最大值。DP起点设置：dp[0][0][0]=1 , 对应空串的状态，长度为0，对应自动机上初始结点，匹配了0个模式串。

细节：1.空间上有限制，需要使用滚动数组，交替使用。dp[i]的状态都是从dp[i-1]转移过来，即长度为i的文本串是通过长度为（i-1）的文本串加上一个字符构成的。所以数组第一维大小只需要2，交替使用即可。一个作为上一次的状态，一个作为当前新的状态。

2.模式串可能重复，插入的时候不能直接覆盖，要累加。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
// AC自动机
int getId(char ch)
{
   if (ch == 'A')
      return 0;
   if (ch == 'T')
      return 1;
   if (ch == 'G')
      return 2;
   return 3;
}
queue<int> q;
int c[MAXN][4], val[MAXN], fail[MAXN], cnt;
void ins(char *s, int index)
{
   int len = strlen(s);
   int now = 0;
   for (int i = 0; i < len; i++)
   {
      int v = getId(s[i]);
      if (!c[now][v])
         c[now][v] = ++cnt;
      now = c[now][v];
   }
   val[now] |= 1 << index; // now 这个结点 代表 的 是第index 个 模式串 二进制状态表示
}
void get_fail_pointer()
{
   for (int i = 0; i < 4; i++)
      if (c[0][i])
         fail[c[0][i]] = 0, q.push(c[0][i]);
   while (!q.empty())
   {
      int u = q.front();
      q.pop();
      for (int i = 0; i < 4; i++)
         if (c[u][i])
            fail[c[u][i]] = c[fail[u]][i], q.push(c[u][i]), val[c[u][i]] |= val[fail[c[u][i]]];
         else
            c[u][i] = c[fail[u]][i];
   }
}

char s[123];
int w[123];
int dp[2][1011][1 << 11];
int cal(int sta)
{
   int res=0;
   int cnt=0;
   while(sta){
      if(sta&1)res+=w[cnt];
      sta>>=1;
      cnt++;
   }
   return res;
}
int main()
{
#ifdef DEBUG
   freopen("1.in", "r", stdin);
   freopen("1.out", "w", stdout);
#endif
   int n, L;
   while (~scanf("%d%d", &n, &L))
   {
      memset(c,0,sizeof(c));
      memset(dp,0,sizeof(dp));
      memset(val,0,sizeof(val));
      cnt=0;
      for (int i = 0; i < n; i++)
      {
         scanf("%s %d", s, &w[i]);
         ins(s, i);
      }
      get_fail_pointer();
      dp[0][0][0] = 1;
      for (int i = 1; i <= L; i++)
      {
         memset(dp[i & 1], 0, sizeof(dp[i & 1]));
         for (int j = 0; j <= cnt; j++)
         {
            for (int i2 = 0; i2 < (1 << n); i2++)
            {
               for (int k = 0; k < 4; k++)
               {
                  if (dp[(i - 1) & 1][j][i2])
                  {
                     dp[i & 1][c[j][k]][i2 | val[c[j][k]]] = 1;
                  }
               }
            }
         }
      }
      int ans = -1e9;

      for (int i2 = 0; i2 < (1 << n); i2++)
      {
         for (int j = 0; j <= cnt; j++)
         {
            if (dp[L & 1][j][i2])
            {
               ans=max(cal(i2),ans);
               break;
            }
         }
      }
      if(ans>=0)
         printf("%d\n",ans);
      else 
         puts("No Rabbit after 2012!");
   }

   return 0;
}