HDU 3341 Lost's revenge(AC 로봇 + DP, 레벨 5)
Crawling in process...
Crawling failed
Time Limit:5000MS Memory Limit:65535KB 64bit IO Format:%I64d & %I64u
Submit
Status
Appoint description: System Crawler (2013-05-30)
Description
Lost and AekdyCoin are friends. They always play "number game"(A boring game based on number theory) together. We all know that AekdyCoin is the man called "nuclear weapon of FZU,descendant of Jingrun", because of his talent in the field of number theory. So Lost had never won the game. He was so ashamed and angry, but he didn't know how to improve his level of number theory.
One noon, when Lost was lying on the bed, the Spring Brother poster on the wall(Lost is a believer of Spring Brother) said hello to him! Spring Brother said, "I'm Spring Brother, and I saw AekdyCoin shames you again and again. I can't bear my believers were being bullied. Now, I give you a chance to rearrange your gene sequences to defeat AekdyCoin!".
It's soooo crazy and unbelievable to rearrange the gene sequences, but Lost has no choice. He knows some genes called "number theory gene"will affect one "level of number theory". And two of the same kind of gene in different position in the gene sequences will affect two "level of number theory", even though they overlap each other. There is nothing but revenge in his mind. So he needs you help to calculate the most "level of number theory"after rearrangement.
Input
There are less than 30 testcases.
For each testcase, first line is number of "number theory gene"N(1<=N<=50). N=0 denotes the end of the input file.
Next N lines means the "number theory gene", and the length of every "number theory gene"is no more than 10.
The last line is Lost's gene sequences, its length is also less or equal 40.
All genes and gene sequences are only contains capital letter ACGT.
Output
For each testcase, output the case number(start with 1) and the most "level of number theory"with format like the sample output.
Sample Input
3
AC
CG
GT
CGAT
1
AA
AAA
0
Sample Output
Case 1: 3
Case 2: 2
: , DP。
#include<cstring>
#include<cstdio>
#include<iostream>
#include<queue>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define clr(f,z) memset(f,z,sizeof(f))
using namespace std;
const int msize=1006;
const int oo=0x3f3f3f3f;
const int sig=4;
class AC_Machine
{
public:int ch[msize][sig],val[msize],f[msize],sz;
void clear()
{
clr(ch[0],0);sz=1;val[0]=0;
}
int idx(char z)
{
if(z=='A')return 0;
if(z=='G')return 1;
if(z=='C')return 2;
if(z=='T')return 3;
}
void insert(char*s,int v)
{
int u=0,c;
for(int i=0;s[i];++i)
{
c=idx(s[i]);
if(!ch[u][c])
{
clr(ch[sz],0);val[sz]=0;
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]+=v;
}
void getFail()
{
int u,v,r;
queue<int>Q;
FOR(c,0,sig-1)
{
u=ch[0][c];
if(u)
{
Q.push(u);f[u]=0;
}
}
while(!Q.empty())
{
r=Q.front();Q.pop();
val[r]+=val[ f[r] ];
FOR(c,0,sig-1)
{
u=ch[r][c];
if(!u)
{
ch[r][c]=ch[ f[r] ][c];continue;
}
v=f[r];Q.push(u);
f[u]=ch[v][c];
}
}
}
};
AC_Machine ac;
/*
class Edge
{
public:
int x,cf[5];
}dp[50][msize];*/
int n,cf[5],len;// i ,j
char s[msize];
/*
void getans()
{
int u,add;
FOR(i,0,len)FOR(j,0,ac.sz-1)
{dp[i][j].x=-1;
FOR(k,0,sig-1)dp[i][j].cf[k]=cf[k];
}
dp[0][0].x=0;
int ret;
FOR(i,1,len)
FOR(j,0,ac.sz-1)
if(dp[i-1][j].x!=-1)
{
FOR(k,0,sig-1)
{
u=ac.ch[j][k];
if(!dp[i-1][j].cf[k])continue;
ret=dp[i-1][j].x+ac.val[u];
dp[i][u].x=max(dp[i][u].x,ret);
FOR(t,0,sig-1)
dp[i][u].cf[t]=dp[i-1][j].cf[t];
--dp[i][u].cf[k];
}
}
int ans=0;
FOR(i,0,ac.sz-1)
ans=max(ans,dp[len][i].x);
//if(ans==oo)ans=-1;
printf("%d
",ans);
}*/
int dp[505][11*11*11*11+9];
int bit[5];
void getans()
{ clr(dp,-1);
bit[0]=(cf[1]+1)*(cf[2]+1)*(cf[3]+1);
bit[1]=(cf[2]+1)*(cf[3]+1);
bit[2]=cf[3]+1;
bit[3]=1;
dp[0][0]=0;
int sss=cf[0]*bit[0]+cf[1]*bit[1]+cf[2]*bit[2]+cf[3]*bit[3];
FOR(A,0,cf[0])FOR(B,0,cf[1])FOR(C,0,cf[2])FOR(D,0,cf[3])
{
//int st=A*bit[0]+B*bit[1];+C*bit[2]+D*bit[3];
int st=A*bit[0]+B*bit[1]+C*bit[2]+D*bit[3];
FOR(i,0,ac.sz-1)
if(dp[i][st]!=-1)
{
FOR(k,0,sig-1)
{
int to=ac.ch[i][k],stu=st+bit[k];
//if(A==2&&C==1&k==2)puts("+++"),printf("%d %d
",st,stu);
if(k==0&&A==cf[0])continue;
if(k==1&&B==cf[1])continue;
if(k==2&&C==cf[2])continue;
if(k==3&&D==cf[3])continue;
//if(stu==sss)puts("yes");
//puts("++++");
//printf("%d %d
",to,ac.val[to]);
dp[to][stu]=max(dp[to][stu],dp[i][st]+ac.val[to]);
// cout<<dp[to][stu]<<endl;
}
}
}
int ans=0;
//cout<<sss<<endl;
FOR(i,0,ac.sz-1)
ans=max(ans,dp[i][sss]);
printf("%d
",ans);
}
int main()
{ int cas=0;
while(~scanf("%d",&n))
{ if(n==0)break;
ac.clear();
FOR(i,1,n)
{
scanf("%s",s);
ac.insert(s,1);
}
ac.getFail();
scanf("%s",s);
clr(cf,0);
len=strlen(s);
for(int i=0;s[i];++i)
++cf[ ac.idx(s[i]) ];
printf("Case %d: ",++cas);
getans();
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.