ZOJ3545 Rescue the Rabbit
发布时间:2020-12-14 03:48:20 所属栏目:大数据 来源:网络整理
导读:分析 未知定长串中不同已知模板串的出现次数问题,一般做法是AC自动机上dp。 考虑背包, (dp(i,j,k)) 表示当前串长为 (i) ,在AC自动机上对应节点 (j) ,已匹配的模板串的状态为 (k) 的情况是否出现。用刷表法向后转移。先枚举不定串长度,再枚举AC
分析未知定长串中不同已知模板串的出现次数问题,一般做法是AC自动机上dp。 考虑背包,(dp(i,j,k))表示当前串长为(i),在AC自动机上对应节点(j),已匹配的模板串的状态为(k)的情况是否出现。用刷表法向后转移。先枚举不定串长度,再枚举AC自动机上节点,然后枚举已知状态,最后枚举字母边转移。 时间复杂度(O(l cdot MaxNode cdot 2^n cdot SigmaSize))。第一维可以滚动,空间复杂度(O(MaxNode cdot 2^n)) 代码#include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<ctime> #include<iostream> #include<string> #include<vector> #include<list> #include<deque> #include<stack> #include<queue> #include<map> #include<set> #include<algorithm> #include<complex> #pragma GCC optimize ("O0") using namespace std; template<class T> inline T read(T&x){ T data=0; int w=1; char ch=getchar(); while(!isdigit(ch)) { if(ch==‘-‘) w=-1; ch=getchar(); } while(isdigit(ch)) data=10*data+ch-‘0‘,ch=getchar(); return x=data*w; } typedef long long ll; const int INF=0x7fffffff; const int MAXN=1010; const int SigmaSize=4; bool dp[2][MAXN][1100]; int mp[15]; struct Trie { int next[MAXN][SigmaSize]; int fail[MAXN]; int end[MAXN]; int root,ncnt; int newnode() { for(int i=0;i<SigmaSize;++i) next[ncnt][i]=-1; end[ncnt++]=0; return ncnt-1; } void init() { ncnt=0; root=newnode(); } int id(char c) { if(c==‘A‘) return 0; else if(c==‘G‘) return 1; else if(c==‘T‘) return 2; else return 3; } void insert(char*str,int v) { int now=root; int len=strlen(str); for(int i=0;i<len;++i) { int c=id(str[i]); if(next[now][c]==-1) next[now][c]=newnode(); now=next[now][c]; } end[now]|=(1<<v); } void getfail() { queue<int>Q; fail[root]=root; for(int i=0;i<SigmaSize;++i) { if(next[root][i]==-1) next[root][i]=root; else { fail[next[root][i]]=root; Q.push(next[root][i]); } } while(!Q.empty()) { int now=Q.front(); Q.pop(); end[now]|=end[fail[now]]; for(int i=0;i<SigmaSize;++i) { if(next[now][i]==-1) next[now][i]=next[fail[now]][i]; else { fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } } void solve(int n,int l) { memset(dp,sizeof(dp)); dp[0][0][0]=1; // dp[len][node][state] int cur=1; for(int i=1;i<=l;++i) { memset(dp[cur],sizeof(cur)); for(int j=0;j<ncnt;++j) { for(int k=0;k<(1<<n);++k) { for(int q=0;q<SigmaSize;++q) { int nxt=next[j][q]; dp[cur][nxt][k|end[nxt]]=(dp[cur][nxt][k|end[nxt]]||dp[cur^1][j][k]); } } } cur^=1; } int ans=-INF; for(int i=0;i<ncnt;++i) for(int j=0;j<(1<<n);++j) { if(dp[cur^1][i][j]) { int sum=0; for(int k=0;k<n;++k) if(j&(1<<k)) sum+=mp[k]; ans=max(ans,sum); } } if(ans<0) printf("No Rabbit after 2012!n"); else printf("%dn",ans); } }AC; char s[110]; int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); int n,l,w; while(~scanf("%d %d",&n,&l)) { AC.init(); for(int i=0;i<n;++i) { scanf("%s %d",s,&w); AC.insert(s,i); mp[i]=w; } AC.getfail(); AC.solve(n,l); } // fclose(stdin); // fclose(stdout); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |