Description
n≤1000 n ≤ 1000
Solution
先n^2做一次最長公共子序列,考慮怎麼求方案
我們對求出的f數組再做一次dp。設g[i,j]為X的前i個和Y的前j個,最長公共子序列長度為f[i,j]的方案數
若i不比對,則g[i,j]+=g[i-1][j]
若i比對,我們從後往前找到第一個X[i]=Y[j]的位置k,g[i,j]+=g[i-1,k-1]。這個東西可以預處理
感覺去年的題有點水啊
Code
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)
const int MOD=1000000007;
const int N=1005;
char a[N],b[N];
int f[N][N],g[N][N];
int pre[N][26];
int main(void) {
scanf("%s",a+1); scanf("%s",b+1);
int n=strlen(a+1),m=strlen(b+1);
rep(i,1,m) {
rep(j,0,25) pre[i][j]=pre[i-1][j];
pre[i][b[i]-'a']=i;
}
int ans=0,prt;// g[0][0]=1;
rep(i,1,n) rep(j,1,m) {
f[i][j]=std:: max(f[i-1][j],f[i][j-1]);
if (a[i]==b[j]) f[i][j]=std:: max(f[i][j],f[i-1][j-1]+1);
}
rep(i,0,n) g[i][0]=1;
rep(i,0,m) g[0][i]=1;
rep(i,1,n) rep(j,1,m) {
if (f[i-1][j]==f[i][j]) (g[i][j]+=g[i-1][j])%=MOD;
int k=pre[j][a[i]-'a']; if (!k) continue;
if (f[i-1][k-1]+1==f[i][j]) {
(g[i][j]+=g[i-1][k-1])%=MOD;
}
}
printf("%d\n", g[n][m]);
return 0;
}