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點都可以考慮放棄之前的狀态，從現在的狀态開始。