Fork me on GitHub

cf1036D

字数统计: 395字   |   阅读时长≈ 1分
转移自老blog

cf1036D

链接

题意

        给你两个串s,t 
        |s|<3e5 |t|<3e5
        允许对两个串进行任意次如下操作：
            选一个区间，用区间和代替整个区间的元素
        最终要求达到s==t
        要求最大化s==t时候的|s|
        若不可能，输出-1

题解

        贪心做法:
            他们俩各自一个指针，往后走，谁小谁先走，不等的话，再来谁小谁先走... 相等时让计数器加1，然后一起走,有解的话输出计数器就是答案了
        其实也是尺取法
        再细细分析
        我们发现可以dp证明，dp[i]代表s串的前i项能否匹配t串的前j项，若能匹配，为dp[i]赋值j，否则定义此dp没有意义
        我们发现有意义的dp,其值关于i单调，无意义的dp，其判断依据，也关于i单调
        于是可以O（n)完成dp
        有意义的dp值的个数就是答案
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要涉及技术：
Java后端开发、聚合支付、
公众号开发、开源爱好者、Linux

联系QQ:2434387555

很惭愧

只做了一点微小的工作
谢谢大家