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

请大神帮我看看 哪里有错啊

Posted by wsql at 2015-01-02 15:49:15 on Problem 3691
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
const int oo=1001;
using namespace std;
int N,K,idx['T'-'A'+1],sz=1,ch[921][4],f[921],dp[1000][921],ans=oo;
bool val[921];
char DNA[1000];
void insert(char *s)
{
	int u=0,n=strlen(s);
	for(int i=0;i<n;i++)
	{
		int c=idx[s[i]-'A'];
		if(!ch[u][c])
		ch[u][c]=sz++;
		val[ch[u][c]]|=val[u];
		u=ch[u][c];
	}
	val[u]=1;
}
void getFail()
{
	queue<int>q;
	f[0]=0;
	for(int c=0;c<4;c++)
	{
		int u=ch[0][c];
		if(u)
		{
			q.push(u);
			f[u]=0;
		}
	}
	while(!q.empty())
	{
		int r=q.front();
		q.pop();
		for(int c=0;c<4;c++)
		{
			int u=ch[r][c],v=f[r];
			if(!u)
			{
				ch[r][c]=ch[v][c];
				continue;
			}
			val[u]|=val[r];
			q.push(u);
			while(v&&!ch[v][c])v=f[v];
			f[u]=ch[v][c];
			val[u]|=val[f[u]];
		}
	}
}
int main()
{
	idx['A'-'A']=0;idx['G'-'A']=1;idx['C'-'A']=2;idx['T'-'A']=3;
	scanf("%d",&N);
	int i,j,n,c;
	memset(ch,0,sizeof(ch));
	memset(val,0,sizeof(val));
	for(i=0;i<N;i++)
	{
		scanf("%s",DNA);
		insert(DNA);
	}
	getFail();
	scanf("%s",DNA);
	n=strlen(DNA);
	for(i=0;i<=n;i++)
	for(j=0;j<sz;j++)
	dp[i][j]=oo;
	dp[0][0]=0;
	for(i=1;i<=n;i++)
	for(j=0;j<sz;j++)
	if(dp[i-1][j]<oo)
	for(c=0;c<4;c++)
	{
		int u=ch[j][c];
		if(!val[u])
		dp[i][u]=min(dp[i][u],dp[i-1][j]+(c!=idx[DNA[i-1]-'A']));
	}
	for(i=0;i<sz;i++)
	if(!val[i])
	ans=min(ans,dp[n][i]);
	if(ans==oo)ans=-1;
	printf("%d",ans);
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator