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 , 2430 阅读

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

inline
block