1622: [Usaco2008 Open]Word Power - #include <Seter> - using namespace Orz;

1622: [Usaco2008 Open]Word Power

Seter posted @ 2011年9月18日 15:40 in BZOJ with tags USACO DP Enumeration , 2422 阅读

 

http://www.zybbs.org/JudgeOnline/problem.php?id=1622

 

RunID User Problem Result Memory Time Language Code Length Submit Time
153387 Seter 1622 Accepted 1788 kb 96 ms C/Edit 778 B 2011-09-18 15:29:26

又一题R1了……好开心……

给定N=1000个不长于L1=1000的母串和M=100个不长于L2=30的子序列,求每个母串包含几个子序列。

朴素很简单:枚举母串和子序列,直接比较,时间复杂度O(NML1)。虽然高达10^8,但是由于数据较弱,常数较小,所以照样很快。

可以有更低的时间复杂度么?答案是肯定的。首先考虑朴素慢在什么地方:直接比较。可以快速找到对于子序列的某一个字符在母串中下一次出现的位置么?用f[i][j]记录某个母串第i个字符后的第一个j在哪里,这个用DP的方法从后向前预处理出来就可以了。预处理复杂度是O(NL1|A|)(|A|表示字母表大小26),计算复杂度是O(NML2),由于L2和|A|都很小,所以时间复杂度较低,直接R1了。

 

#include <stdio.h>
#include <string.h>
short n,m,f[1002][26],l[1000];
char a[1000][1002],b[100][31];
inline toalpha(x){return x>='A'&&x<='Z'?x-'A':x>='a'&&x<='z'?x-'a':-1;}
main(){
	short i,j,x,y,s;
	scanf("%hd%hd",&n,&m);
	for(i=n;i--;){
		while((a[i][1]=toalpha(getchar()))==-1);
		for(l[i]=1;(a[i][++l[i]]=toalpha(getchar()))!=-1;);
	}for(i=m;i--;){
		while((b[i][0]=toalpha(getchar()))==-1);
		for(j=0;(b[i][++j]=toalpha(getchar()))!=-1;);
	}for(i=n;i--;){
		memset(f,-1,sizeof(f));
		for(x=l[i];x--;){
			memcpy(f[x],f[x+1],sizeof(f[0]));
			f[x][a[i][x+1]]=x+1;
		}for(s=j=m;j--;)for(x=y=0;b[j][y]!=-1&&((x=f[x][b[j][y++]])!=-1||(s--,0)););
		printf("%hd\n",s);
	}return 0;
}
By Seter

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee