雅礼NOIP模拟 B

题意：给出长度分别为$n$和$m$的字符串$s$和$t$，要求分别从中取出$k$个子串，在相对位置不变的情况下让两个字符串的子串两两相同。求这$k$个子串的最长总长度 ------------ 一开始想的是$f[i][j][k]$表示$s$串到第$i$位，$t$串到第$j$位，取了$k$个子串的最大长度 发现没法转移 那就再加一维 $f[i][j][k][0/1]$表示$s$串到第$i$位，$t$串到第$j$位，取了$k$个子串，$s_i$和$t_j$是否都被选的最长长度 然后就可以愉快地转移了 ``` #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1005; char s[N],t[N]; int n,m,p,f[N][N][12][2]; inline void Chkmax(int &a,int b){if (a<b) a=b;} int main() { scanf("%d%d%d%s%s",&n,&m,&p,s+1,t+1); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int k=1;k<=p;k++) { Chkmax(f[i][j][k][0],max(f[i-1][j][k][0],f[i-1][j][k][1])); Chkmax(f[i][j][k][0],max(f[i][j-1][k][0],f[i][j-1][k][1])); if (s[i]==t[j]) Chkmax(f[i][j][k][1],max(f[i-1][j-1][k][1],max(f[i-1][j-1][k-1][0],f[i-1][j-1][k-1][1]))+1); } printf("%d\n",max(f[n][m][p][0],f[n][m][p][1])); return 0; } ```