Codeforces Round #683 (Div. 2)D. Catching Cheaters

原题地址

题意：

给出一个长度为n的串a和长度为m的串b，仅含小写字母，要求找到a的一个子串c和b的一个子串d，使得两个串的权值：4*LCS(c,d)-| c |-|d | 最大。

其中LCS表示最长公共子序列的长度。| x| 表示串x的长度

1 ≤ m , n ≤ 5000 1 \leq m,n \leq 5000 1≤m,n≤5000

题解：

设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示以 a i a_i ai​结尾的子串和 b j b_j bj​ 结尾的子串的最大权值。

那么如果 a i a_i ai​ ≠ \not= ​= b j b_j bj​:

d p [ i ] [ j ] = m a x ( m a x ( d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j ] ) − 1 , − 2 ) dp[i][j]=max(max(dp[i][j-1],dp[i-1][j])-1,-2) dp[i][j]=max(max(dp[i][j−1],dp[i−1][j])−1,−2)

公式第一层max的第一部分表示，从之前的状态转移过来，但是由于当前 a i a_i ai​ ≠ \not= ​= b j b_j bj​

所以转移过来只是徒增长度，权值减1。第二部分表示放弃之前的状态，从当前状态开始(最大子段和的思想)

否则:

d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j − 1 ] + 2 , 2 ) dp[i][j]=max(dp[i-1][j-1]+2,2) dp[i][j]=max(dp[i−1][j−1]+2,2)

同理第一部分表示，表示从之前的状态转移过来，两个串的长度都加1了，但是最长公共子序列的长度显然也加1了，总体贡献加2，第二部分表示放弃之前状态从当前开始，这种情况就是两个串都只有一个字母并且相等，所以权值为2。

其他思考：

构造矩阵e

如果 a i a_i ai​= b j b_j bj​ : e [ i ] [ j ] e[i][j] e[i][j]=1

否则 e [ i ] [ j ] e[i][j] e[i][j] =0

那么模型转化，两个1之间的边权等于曼哈顿距离的相反数，每个1的点权等于1，每个1与其右下角(不包含同行同列)的1之间有有向边。

问题转化：找一条路径使得权值最大，路径的权值等于路径上的所有点边权值之和。所求答案即为最大权值-2。

如果只考虑在1之间走动那么问题很难处理，每一个1都可能被左上角（不含同行同列）的每一个1所转移，虽然有些显然不是最优可以忽略，但是剩下的依然很难转移，可转移的点很多，或者说从复杂度上来讲就是不成立的。

如果考虑0点也可以走，那么问题就好考虑了，0点不同于1点的仅仅是点权为0。

但是注意1点只能从左上角的那个点转移过来，不然不符合要求。

而0点可以从上面或者左边的点转移过来，也可以从左上（但是与两步走等价），这样所得到的状态方程与上面正解相同。

当然不管是0点还是1点都可以考虑放弃之前的状态，从现在的状态开始。