Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

上面的数据全对了却WA，什么情况

Posted by shadowxuhao at 2013-04-09 19:19:45 on Problem 3691
In Reply To:贴几个数据…… Posted by:peargobble at 2011-07-05 22:44:36
```#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define maxn 1010
#define CH 4
#define inf 1000000000
int chd[maxn][CH+1];
int fail[maxn],val[maxn];
int sz;
int id[90];
char son[5]={'*','A','C','G','T'};
int min(int a,int b)
{
return a<b?a:b;
}
void init(){
memset(chd[0],0,sizeof(chd[0]));
sz=1;
val[0]=0;
return;
}
void insert(char s[]){
int i=0,p=0;
int len=strlen(s);
for(i=0;i<=len-1;i++)
{
int x=id[s[i]];
if(!chd[p][x]){
memset(chd[sz],0,sizeof(chd[sz]));
val[sz]=0;
chd[p][x]=sz++;
}
p=chd[p][x];
}
val[p]=1;
return;
}
void build_fail(){
queue<int> que;
for(int i=1;i<=CH;i++)
if(chd[0][i])
{
fail[chd[0][i]]=0;
que.push(chd[0][i]);
}
while(!que.empty())
{
int p=que.front();
que.pop();
for(int i=1;i<=CH;i++)
{
if(chd[p][i])
{
int v=chd[p][i];
que.push(v);
fail[v]=chd[fail[p]][i];
val[v]|=val[fail[v]];
}
else
{
chd[p][i]=chd[fail[p]][i];
}
}
}
return;
}
int dp[1010][1010];
int main(){
int i,j,k;
id['A']=1;id['C']=2;id['G']=3;id['T']=4;
int n,cases=0;
char tmp[30],s[1010];
scanf("%d",&n);
getchar();
while(n!=0)
{
init();
for(i=1;i<=n;i++)
{
gets(tmp);
insert(tmp);
}
build_fail();
gets(s+1);
int len=strlen(s);
len--;
for(i=0;i<=len;i++)
for(j=0;j<=sz-1;j++)
dp[i][j]=inf;
dp[0][0]=0;
for(i=0;i<=len-1;i++)
for(j=0;j<=sz-1;j++)
{
if(dp[i][j]!=inf && !val[j])
{
for(k=1;k<=4;k++)
{
if(!val[chd[j][k]])
{
dp[i+1][chd[j][k]]=min(dp[i+1][chd[j][k]],dp[i][j]+(s[i+1]!=son[k]));

}

}
}

}
int ans=inf;
for(j=0;j<=sz-1;j++)
if(dp[len][j]<ans)
ans=dp[len][j];
if(ans==inf)
printf("-1\n");
else
printf("Case %d: %d\n",++cases,ans);
scanf("%d",&n);
getchar();
}
return 0;
}
```

Followed by: