hdu 4057(ac自动机+状态压缩dp)

时间:2021-12-13 23:58:04

题意:容易理解...

分析:题目中给的模式串的个数最多为10个,于是想到用状态压缩dp来做,它的状态范围为1-2^9,所以最大为2^10-1,那我们可以用:dp[i][j][k]表示长度为i,在trie树上的状态为j,压缩后的状态为k时的情况,知道怎么压缩之后这道题就是一道简单的ac自动机+压缩dp题了。

代码实现:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
struct node{
int next[];
int fail;
int flag;
void init()
{
memset(next,,sizeof(next));
fail=;
flag=;
}
}a[]; int n,len,tot;
int weight[];
char keyword[];
int dp[][][<<]; void chushihua()
{
tot=;
a[].init();
memset(dp,,sizeof(dp));
} int hash(char x)
{
if(x=='A')
return ;
else if(x=='C')
return ;
else if(x=='G')
return ;
else
return ;
} void insert(char *str,int biaohao)
{
int p=,index;
for(;*str!='\0';str++)
{
index=hash(*str);
if(a[p].next[index]==)
{
a[++tot].init();
a[p].next[index]=tot;
}
p=a[p].next[index];
}
a[p].flag=a[p].flag|(<<biaohao);//状态标记
} void build_fail()//建立trie图
{
queue<int>Q;
int p,son,cur,i;
Q.push();
while(!Q.empty())
{
p=Q.front();
Q.pop();
for(i=;i<;i++)
{
if(a[p].next[i]!=)
{
son=a[p].next[i];
cur=a[p].fail;
if(p==)
a[son].fail=;
else
{
while(cur&&a[cur].next[i]==)
cur=a[cur].fail;
a[son].fail=a[cur].next[i];
}
a[son].flag=a[son].flag|a[a[son].fail].flag;
Q.push(son);
}
else
a[p].next[i]=a[a[p].fail].next[i];
}
}
} int get_weight(int x)
{
int i,sum=;
for(i=;i<n;i++)
if(x&(<<i))
sum+=weight[i];
return sum;
} void solve()
{
int i,j,k,l,son,res,temp;
dp[][][]=;
for(i=;i<=len;i++)
{
memset(dp[i&],,sizeof(dp[i&]));
for(j=;j<=tot;j++)
{
for(l=;l<(<<n);l++)
{
if(dp[(i+)&][j][l]!=)
continue;
for(k=;k<;k++)
{
son=a[j].next[k];
dp[i&][son][l|a[son].flag]=;
}
}
}
}
res=-;
for(j=;j<(<<);j++)
for(i=;i<=tot;i++)
if(dp[len&][i][j]==)
{
temp=get_weight(j);
if(res<temp)
res=temp;
}
if(res<)
printf("No Rabbit after 2012!\n");
else
printf("%d\n",res);
} int main()
{
int i;
while(scanf("%d%d",&n,&len)!=EOF)
{
chushihua();
getchar();
for(i=;i<n;i++)
{
scanf("%s%d",keyword,&weight[i]);
insert(keyword,i);
getchar();
}
build_fail();
solve();
}
return ;
}