我努力奔跑,只为追上曾经被寄予厚望的自己

雅礼NOIP模拟 B

2018-11-07 13:54:42


题意:给出长度分别为 $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;
}