首页 > 其他分享 >CF1363F题解

CF1363F题解

时间:2022-09-20 19:24:13浏览次数:68  
标签:正义 串到 题解 字母 CF1363F 操作

好妙的dp
-1的情况就是字母构成的可重集不同
我们将一次操作抽象成将一个字符向前移动若干格
我们设f[i][j]表示s串到了第i个字母,t串到了第j个字母的最小操作次数
1.将第i个字母移到前面去,f[i][j]=f[i-1][j]+1
注意,如果前面没有合适的位置,那这个操作就多算了,一定不是最优的,不会被记入答案
2.直接匹配(s[i]=t[j]) f[i][j]=f[i-1][j-1]
3.后面的字母天降正义与t[j]匹配
首先我们需要判断是否有可以天降正义的字母,然后贡献会在后面的1操作算
所以直接f[i][j]=f[i][j-1]即可

标签:正义,串到,题解,字母,CF1363F,操作
From: https://www.cnblogs.com/CHK666/p/16712180.html

相关文章

  • Codeforces #821 Div2(A~D2)题解
    CF#821Div2AConsecutiveSum题目:​ 选择\(i\)和\(j\),如果\(j=i+xk(x=R)\),可以交换\(i,j\)。任意选择一段长度为k的相加。思路:​ 题目等价于在下标\(mod\)k相同......
  • CGR1 简要题解
    G.Tree-Tac-Toe瞎扯:首先一看黑就不可能赢,最多争个平。若有度数大于\(3\)的点白直接赢了。若一个点度数为\(3\),且只有不多于\(1\)端是叶子,白也赢了。所以现在树的形......
  • js精度计算问题解决,Jsutil库源码
    为什么会存在浮点数计算精度丢失问题,这个原因不再过多赘述; JS中如何解决精度计算问题,大不部分人都知道升幂再降幂的解决方案; 但是如果直接升幂也会出现精度问题,且需......
  • sb课件的题解(复习)
    sb课件的题解(复习)不理解,为什么一个新的课件我就2题没做过,没救了CF1310C这题,我们发现它不同的子段共有\(n*(n-1)/2\)个,将其按字典序排序我们需要便捷的比较,考虑维护\(......
  • 【题解】CF1733E - Conveyor
    因为每秒只放一个球,所以对于每一个\(x+y=a\)的对角线最多只有一个球且任意两个球不会相遇,所以我们只用知道第\(t-x-y\)秒放的球的移动路径即可。等价于需要求出前\(......
  • CF round 812 div2 A-D 题解
    首先第一题TravelingSalesManProblem,给出一些坐标,就是问从原点出发,然后收集所有的点,问最少需要多少次移动这个就是求收集完那曼哈顿距离,这个距离稍加观察可以发现,就是......
  • EFCore 6级联删除问题解决Database operation expected to affect 1 row(s) but actua
    异常信息:Databaseoperationexpectedtoaffect1row(s)butactuallyaffected0row(s).Datamayhavebeenmodifiedordeletedsinceentitieswereloaded.See......
  • SP2128题解
    题意共有\(t\)个\(n\timesm\)的由.、x、o组成的字符矩阵。设矩阵中连续\(k\)格为x小A加一分,连续\(k\)格为o小B加一分。正文\(\Large{时间复杂度:}\l......
  • 【Coel.解题报告】【没事找事】CSP-S2 真题解析
    昨天刚考完CSP-S1,反正没什么想做的(最近好颓废…),来复盘一下。本次比赛评价(转载):CSP-S1是由CCF自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「基数排序......
  • 牛客题解 珂朵莉与宇宙
    链接:https://ac.nowcoder.com/acm/problem/14600来源:牛客网题解作者岛田小雅这道题很仁慈地直接告诉了我们子区间的个数,如果直接暴力遍历所有的子区间,复杂度是\(O(\f......