题意理解 从字符串 AAA 中选一个子串 CCC，从 BBB 中选一个子串 DDD，最大化相似度得分： S(C,D)=4⋅LCS(C,D)−∣C∣−∣D∣S(C,D) = 4 \cdot LCS(C,D) - |C| - |D| S(C,D)=4⋅LCS(C,D)−∣C∣−∣D∣ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 思路分析 关键观察： 如果固定 LCS 的匹配位置，为最大化得分，CCC 和 DDD 应该恰好覆盖这些匹配位置（最短子串）。 设 LCS 的匹配点在 AAA 中是 i1<i2<⋯<iki_1 < i_2 < \cdots < i_ki1 <i2 <⋯<ik ，在 BBB 中是 j1<j2<⋯<jkj_1 < j_2 < \cdots < j_kj1 <j2 <⋯<jk 。 则 ∣C∣=ik−i1+1|C| = i_k - i_1 + 1∣C∣=ik −i1 +1，∣D∣=jk−j1+1|D| = j_k - j_1 + 1∣D∣=jk −j1 +1。 得分可以分解为：第一个匹配贡献 222，之后每个匹配 (it,jt)(i_t, j_t)(it ,jt ) 贡献 4−(it−it−1)−(jt−jt−1)4 - (i_t - i_{t-1}) - (j_t - j_{t-1})4−(it −it−1 )−(jt −jt−1 )。 设 dp[i][j]dp[i][j]dp[i][j] 表示以 (i,j)(i, j)(i,j) 为最后一个匹配点（A[i]=B[j]A[i] = B[j]A[i]=B[j]）时的最大得分。 状态转移（A[i]=B[j]A[i] = B[j]A[i]=B[j] 时）： dp[i][j]=max⁡(2,max⁡i′<i,j′<j(dp[i′][j′]+4−(i−i′)−(j−j′)))dp[i][j] = \max(2, \max_{i'<i,j'<j}(dp[i'][j'] + 4 - (i-i') - (j-j'))) dp[i][j]=max(2,i′<i,j′<jmax (dp[i′][j′]+4−(i−i′)−(j−j′))) 令 g[i][j]=dp[i][j]+i+jg[i][j] = dp[i][j] + i + jg[i][j]=dp[i][j]+i+j，则转移变为： dp[i][j]=max⁡(2,max⁡i′<i,j′<j(g[i′][j′])+4−i−j)dp[i][j] = \max(2, \max_{i'<i,j'<j}(g[i'][j']) + 4 - i - j) dp[i][j]=max(2,i′<i,j′<jmax (g[i′][j′])+4−i−j) 用前缀最大值优化，可以做到 O(nm)O(nm)O(nm)。 答案： 所有 dp[i][j]dp[i][j]dp[i][j] 的最大值，若无匹配则为 000 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 参考代码