HDu 4057(acオートマチック、状態圧縮dp)
Rescue the Rabbit
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1790 Accepted Submission(s): 512
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
Sample Output
題意:いくつかのモード列を与えて、各列は一定の価値があって、今1つの長さMの列を構築して、最大の価値がいくらで、各モード列は最大1回統計します.
まず文字列のマッチングに関し,acオートマチックを用い,次に最大価値を求めるには状態圧縮dpで解決する.ネット上の様々なブログでは、この問題をはっきり説明している人は一人もいません.
まずacオートマチックについてお話ししましょう.acオートマチックの2次元配列シミュレーションを確立し、val[]配列で各サブ列の終了を表します.(ただし、格納数は1,2,3,4,5ではありません.これらは、後で状態圧縮dpを使うので、ここでは2^i、すなわちコードの1<そしてオートマチックを確立する過程であり、通常の確立とは差は多くないが、val配列に変動があるだけである.一つのサブストリングが終わってちょうど別のサブストリングにつながったときに相当するため、val[]は変わらないのだろうか.変わらなければacオートマチックを確立するのは意味がない.val[ ch[p][i] ] | = val[ f [ ch [p][i] ] ];(f[]配列は不整合ポインタ配列)1つのサブストリングの末尾ノードのval値は必ず1から1<そしてdp部分では,状態をdp[i][j][k]で表し,長さiのacオートマトンにおけるj番目のノードへの対応状態をkとする(もちろんkは必ずバイナリの目で見て,0はあるサブストリングが存在しないことを示し,1は存在することを示す)状態が成立するか否かを構成し,成立すれば1に等しくし,そうでなければ継続する.
if(dp[(i+1)&1][j][hh]) dp[i&1][ch[j][k]][hh|val[ch[j][k]]]=1;
これはdp部分のエッセンスです.前の状態が成立した後、次の状態を代表して押し出すことができる状態も必然的に成立するので、押し出されたval[ch[j][k]]は私がなぜ上記のようにvalを格納するのかを紹介した理由で、あるノードがどれだけのサブストリングを含むかのすべての情報を記録しています.(もちろんバイナリに変換した後、1はありますが、0はありません)
もちろん,空間はメモリを爆発させることができないため,配列をスクロールする方式でdp[i][j][k]のiを2つだけ開き,シミュレーションに相当するとともにメモリを大幅に削減した.
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1790 Accepted Submission(s): 512
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.
題意:いくつかのモード列を与えて、各列は一定の価値があって、今1つの長さMの列を構築して、最大の価値がいくらで、各モード列は最大1回統計します.
まず文字列のマッチングに関し,acオートマチックを用い,次に最大価値を求めるには状態圧縮dpで解決する.ネット上の様々なブログでは、この問題をはっきり説明している人は一人もいません.
まずacオートマチックについてお話ししましょう.acオートマチックの2次元配列シミュレーションを確立し、val[]配列で各サブ列の終了を表します.(ただし、格納数は1,2,3,4,5ではありません.これらは、後で状態圧縮dpを使うので、ここでは2^i、すなわちコードの1<
if(dp[(i+1)&1][j][hh]) dp[i&1][ch[j][k]][hh|val[ch[j][k]]]=1;
これはdp部分のエッセンスです.前の状態が成立した後、次の状態を代表して押し出すことができる状態も必然的に成立するので、押し出されたval[ch[j][k]]は私がなぜ上記のようにvalを格納するのかを紹介した理由で、あるノードがどれだけのサブストリングを含むかのすべての情報を記録しています.(もちろんバイナリに変換した後、1はありますが、0はありません)
もちろん,空間はメモリを爆発させることができないため,配列をスクロールする方式でdp[i][j][k]のiを2つだけ開き,シミュレーションに相当するとともにメモリを大幅に削減した.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;
typedef long long ll;
const int CH =4,NODE = 1005;
int m,n;
int idx(char x)
{
if(x=='A')return 0;
else if(x=='C')return 1;
else if(x=='G')return 2;
return 3;
}
int ch[NODE][CH],f[NODE],val[NODE],sz,v[NODE];
int node()
{
memset(ch[sz],0,sizeof(ch[sz]));
val[sz]=0;
return sz++;
}
void init()
{
sz=0;
node();
memset(f,0,sizeof(f));
}
void ins(char *s,int i)
{
int u=0;
for(; *s; s++)
{
int c=idx(*s);
if(!ch[u][c])
ch[u][c]=node();
u=ch[u][c];
}
val[u]=1<<i;
}
int queu[NODE];
void getfail()
{
int l=0,r=0;
queu[r++]=0;
while(l<r)
{
int p=queu[l++];
for(int i=0; i<4; i++)
{
if(ch[p][i]==0)
ch[p][i]=ch[f[p]][i];
else
{
int q=ch[p][i];
if(p)
f[q]=ch[f[p]][i];
val[q]|=val[f[q]];
queu[r++]=q;
}
}
}
}
bool dp[2][1005][1<<10];
int get(int x)
{
int ans=0;
for(int i=0; i<(1<<n); i++)
if(x&(1<<i))//
ans+=v[i];
return ans;
}
void solve()
{
memset(dp,0,sizeof(dp));
dp[0][0][0]=1;
for(int i=1; i<=m; i++)
{
memset(dp[i&1],0,sizeof(dp[i&1]));
for(int j=0; j<=sz; j++)
{
for(int k=0; k<4; k++)
{
for(int hh=0; hh<(1<<n); hh++)
if(dp[(i+1)&1][j][hh])
dp[i&1][ch[j][k]][hh|val[ch[j][k]]]=1;
}
}
}
int ans=-999999999;
for(int i=0; i<=sz; i++)
for(int j=0; j<(1<<n); j++)
if(dp[m&1][i][j])
ans=max(ans,get(j));
if(ans<0)
printf("No Rabbit after 2012!
");
else printf("%d
",ans);
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
for(int i=0; i<n; i++)
{
char ss[105];
scanf("%s%d",ss,&v[i]);
ins(ss,i);
}
getfail();
solve();
}
return 0;
}