程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4057 Rescue the Rabbit (AC自動機+DP)

HDU 4057 Rescue the Rabbit (AC自動機+DP)

編輯：C++入門知識

HDU 4057 Rescue the Rabbit (AC自動機+DP)

Rescue the Rabbit
Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1482    Accepted Submission(s): 430

Problem Description Dr. X is a biologist, who likes rabbits very much and can do everything for them. 2012 is coming, and Dr. X wants to take some rabbits to Noah's Ark, or there are no rabbits any more.

A rabbit's genes can be expressed as a string whose length is l (1 ≤ l ≤ 100) containing only 'A', 'G', 'T', 'C'. There is no doubt that Dr. X had a in-depth research on the rabbits' genes. He found that if a rabbit gene contained a particular gene segment, we could consider it as a good rabbit, or sometimes a bad rabbit. And we use a value W to measure this index.

We can make a example, if a rabbit has gene segment ATG, its W would plus 4; and if has gene segment TGC, its W plus -3. So if a rabbit's gene string is ATGC, its W is 1 due to ATGC contains both ATG(+4) and TGC(-3). And if another rabbit's gene string is ATGATG, its W is 4 due to one gene segment can be calculate only once.

Because there are enough rabbits on Earth before 2012, so we can assume we can get any genes with different structure. Now Dr. X want to find a rabbit whose gene has highest W value. There are so many different genes with length l, and Dr. X is not good at programming, can you help him to figure out the W value of the best rabbit.

Input There are multiple test cases. For each case the first line is two integers n (1 ≤ n ≤ 10)，l (1 ≤ l ≤ 100), indicating the number of the particular gene segment and the length of rabbits' genes.

The next n lines each line contains a string DNAi and an integer wi (|wi| ≤ 100), indicating this gene segment and the value it can contribute to a rabbit's W.

Output For each test case, output an integer indicating the W value of the best rabbit. If we found this value is negative, you should output No Rabbit after 2012!.

Sample Input

2 4
ATG 4
TGC -3

1 6
TGC 4

4 1
A -1
T -2
G -3
C -4

Sample Output

4
4
No Rabbit after 2012!

Hint
case 1：we can find a rabbit whose gene string is ATGG(4), or ATGA(4) etc.
case 2：we can find a rabbit whose gene string is TGCTGC(4), or TGCCCC(4) etc.
case 3：any gene string whose length is 1 has a negative W.

Author HONG, Qize
Source 2011 Asia Dalian Regional Contest

題意：

有ATCG4個字母，要求構成一個長度為l的字符串，給出n個模式串及其權值，問能構成的字符串中最大的權值和是多少，每個模式串只計算一次。

分析：

很容易想到是AC自動機。我們在AC自動機上找到長度為l的可行方案，並求出最大值即可。用dp[i][j][k]表示字符串長度為i時，AC自動機上第j個結點是否可達狀態k。因為模式串只有10種，所以最多有2^10個狀態，狀壓一下就行了，然後就是長度為i的字符串只由第i-1個變過來，所以可以用滾動數組。

/*
 *
 * Author : fcbruce 
 *
 * Time : Thu 13 Nov 2014 08:23:41 PM CST
 *
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#define sqr(x) ((x)*(x))
#define LL long long
#define itn int
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
#define eps 1e-10

#ifdef _WIN32
  #define lld %I64d
#else
  #define lld %lld
#endif

#define maxm 
#define maxn 1007

using namespace std;

char gene[17][233];
int w[17];
int dp[2][maxn][2333];

int q[maxn<<1];

const int maxsize = 4;
struct ACauto
{
  int ch[maxn][maxsize];
  int val[maxn],last[maxn],nex[maxn];
  int sz;

  ACauto()
  {
    sz=1;
    val[0]=0;
    memset(ch[0],0,sizeof ch[0]);
  }

  void clear()
  {
    sz=1;
    val[0]=0;
    memset(ch[0],0,sizeof ch[0]);
  }

  int idx(char c)
  {
    switch (c)
    {
      case 'A': return 0;
      case 'T': return 1;
      case 'C': return 2;
      case 'G': return 3;
    }
  }

  void insert(const char *s,int v)
  {
    int u=0;
    for (int i=0;s[i]!='';i++)
    {
      int c=idx(s[i]);
      if (ch[u][c]==0)
      {
        memset(ch[sz],0,sizeof ch[sz]);
        val[sz]=0;
        ch[u][c]=sz++;
      }
      u=ch[u][c];
    }
    val[u]=v;
  }

  void get_fail()
  {
    int f=0,r=-1;
    nex[0]=0;
    for (itn c=0;c=0) printf(%d
,MAX);
    else puts(No Rabbit after 2012!);
  }


  return 0;
}