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

这是一道水题……直接DP+容斥原理乱搞就可以AC……但是我足足做了4小时，被Tim大神从头BS到脚才做出来……

这次我的程序写的不是很难看……所以不写题解了……直接看代码吧……

不过这个故事告诉我们几个道理：

1.不要随便贴原来的代码……要贴也看清楚题目再贴……

2.大神都很喜欢BS弱菜……

3.作为弱菜也不要随便怀疑自己的代码……可能是输入错了囧……gets不行就上scanf罢……反正ACC爆低了……

4.对拍！！错了就拍！！对了也拍！！要是拍了我就可以发现我的第一个代码是对的了啊！！

5.要写题解……避免自己看不懂自己的代码……

于是我就写了这个……

#include <stdio.h>
#define maxn 5010
char a[maxn]=".",b[maxn]=".";
int f[2][maxn][2];
main(){
	int i,j;
	scanf("%s%s",a+1,b+1);
	f[0][0][1]=f[1][0][1]=1;
	for(i=0;b[i];i++)f[0][i][1]=1;
	for(i=1;a[i];i++)for(j=1;b[j];j++){
		if(a[i]==b[j]){
			f[i&1][j][0]=f[i&1^1][j-1][0]+1;
			f[i&1][j][1]=f[i&1^1][j-1][1];
			if(f[i&1^1][j][0]>f[i&1][j][0]){
				f[i&1][j][0]=f[i&1^1][j][0];
				f[i&1][j][1]=f[i&1^1][j][1];
			}else if(f[i&1^1][j][0]==f[i&1][j][0]){
				f[i&1][j][1]+=f[i&1^1][j][1];
				f[i&1][j][1]%=100000000;
			}if(f[i&1][j-1][0]>f[i&1][j][0]){
				f[i&1][j][0]=f[i&1][j-1][0];
				f[i&1][j][1]=f[i&1][j-1][1];
			}else if(f[i&1][j-1][0]==f[i&1][j][0]){
				f[i&1][j][1]+=f[i&1][j-1][1];
				f[i&1][j][1]%=100000000;
			}
		}else{
			f[i&1][j][0]=f[i&1^1][j][0];
			f[i&1][j][1]=f[i&1^1][j][1];
			if(f[i&1][j-1][0]>f[i&1][j][0]){
				f[i&1][j][0]=f[i&1][j-1][0];
				f[i&1][j][1]=f[i&1][j-1][1];
			}else if(f[i&1][j-1][0]==f[i&1][j][0]){
				f[i&1][j][0]=f[i&1][j-1][0];
				f[i&1][j][1]+=f[i&1][j-1][1];
				if(f[i&1^1][j-1][0]==f[i&1][j][0])f[i&1][j][1]-=f[i&1^1][j-1][1];
				f[i&1][j][1]%=100000000;
			}
		}
	}printf("%d\n%d\n",f[i&1^1][j-1][0]-1,f[i&1^1][j-1][1]);
	return 0;
}

• inline
• block