【GDOI2018模拟7.10】C

Description

Input

Output

一行表示答案

Sample Input

aa ab

Sample Output

2

Solution

这题直接递归暴力就行了 设暴力带3个参数x,y,l表示上面到x，下面到y，匹配长度为l 预处理一些东西，比如上面第x个字符匹配下面第y个字符之后的第一个是哪个等 加记忆化 就可以过了

Code

#include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) #define N 1010 #define mo 1000000007 using namespace std; int n,m,f[N][N],a[N][N],bz[30],bb[N][N]; char s[N],t[N]; long long ans,hh[N][N]; void dg(int x,int y,int l) { if(x>n||y>m) return; if(l<f[x][y]) return; if(bb[x][y]) { ans=(ans+hh[x][y])%mo; return; } bb[x][y]=1; if(l==f[n][m]) { ans=(ans+1)%mo; hh[x][y]=1; return; } hh[x][y]=ans; dg(x+1,y,l); if(a[x+1][y]!=0) dg(x+1,a[x+1][y],l+1); hh[x][y]=(ans-hh[x][y]+mo)%mo; } int main() { scanf("%s\n%s\n",s+1,t+1); n=strlen(s+1);m=strlen(t+1); fo(i,1,n) fo(j,1,m) { f[i][j]=max(f[i][j-1],f[i-1][j]); if(s[i]==t[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1); } fd(j,m,0) { fo(i,1,n) a[i][j]=bz[s[i]-97]; if(j>0) bz[t[j]-97]=j; } dg(0,0,0); printf("%lld",ans); }