526互联

Text Editor (CF2E) (DP字符串2端分别dp)

发布时间 2023-04-20 16:21:27作者: VxiaohuanV

 

 思路:

  • 首先贪心出性质, 通过模拟这个题意,一定是先右边弄完在去左边弄, 或者左弄完去右边弄,
  • 于是左右2边分别dp一次 然后求和
  • dp[i][j],表示i 和 j 匹配的时的 最小操作次数 
  • 转移的时候有一个贪心结论,当 si != tj 时, 这个贡献时一个固定值, 正向:首先i- (公共的), 反向 : 就是 (n-i)..., 大盖这个意思
  • 等于就不用增加操作