传智杯(省赛第三题)小苯的ovo (详细版)

devtools/2025/3/14 0:51:23/

系列文章目录

传智杯,蓝桥杯动态规划类题型解析(简易题)


文章目录

  • 系列文章目录
  • 前言
  • 一、什么是动态规划
  • 二、核心思想:
  • 三、本题具体实现:
  • 四、完整代码实现:
  • 总结


前言

   这道题其实是我最想总结的一道,因为我拿到这个题,我直接想的是如何修改字符串当中的字符(就很离谱),想了解字符串内容的请见我String,StringBuffer,StringBuilder的区别那一篇,但是看到“最多”这类字眼我就知道事情不简单了,虽然DP类的题我们知道很难,包括我自己碰见动态规划的题也会傻脸,但是我们还是要知道最基础的解法,下面我们来详细的解读一下。


提示:以下是本篇文章正文内容,下面案例可供参考

题目参考:

题目输入输出样例:

一、什么是动态规划

      动态规划(Dynamic Programming,简称 DP)是一种用于求解最优化问题的方法,它通过将问题分解为子问题并逐步求解这些子问题来优化问题的解决过程。动态规划适用于那些可以通过将问题分解为重叠子问题来解决的问题。

动态规划的核心思想:
  1. 最优子结构:问题的最优解可以通过子问题的最优解来构建。
  2. 重叠子问题:子问题会被重复计算,因此通过记忆化(存储子问题的答案)来避免重复计算,从而节省时间。

动态规划的目标是通过将大问题转化为小问题的求解,最终得到最优解。

动态规划的做题步骤
  1. 定义状态:将问题转化为状态表示,通常是通过一个数组或二维数组来表示问题的各个状态。
  2. 状态转移方程:根据问题的约束条件,推导出从一个状态到另一个状态的转移规律。
  3. 边界条件:确定递归的终止条件或基础情况。
  4. 优化:如果有冗余的计算,可以通过空间优化或减少状态存储的维度等手段进一步优化。

           常见的模板就有:

java">public int dpSolution(int n) {int[] dp = new int[n + 1];// 初始化边界条件dp[0] = 0;  // 或者其他适当的值dp[1] = 1;  // 或者其他适当的值// 状态转移方程for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];  // 这是一个示例,根据具体问题的状态转移方程修改}return dp[n];  // 返回最终的结果
}

二、核心思想:

       这道题其实真的挺有难度的在我看来,因为这道题如果暴力去写的话,求最大我们要枚举出很多很多种情况,这显然是不现实的,可能会用递归来一直重复此过程,而这道题选择动态规划显然是必要的:

    

  1. 最优子结构
    要最大化"ovo"的数量,每个位置的选择(是否消耗修改次数形成ovo)会影响后续决策。通过将全局问题拆解为“是否在第i位结束一个ovo”的子问题,可以利用子问题的最优解组合得到全局最优解。

  2. 重叠子问题
    不同位置的决策可能涉及相同的修改次数和字符检查(例如连续多个ovo可能共享部分计算),动态规划通过存储中间状态避免重复计算,提升效率。

  3. 资源分配
    修改次数k是有限资源,动态规划的二维状态dp[i][j]能精确追踪:处理到第i个字符时,消耗j次修改能达到的最大ovo数,从而高效分配修改资源。

  4. 无后效性
    一旦确定i位置的状态(如使用j次修改),后续决策仅依赖当前状态,不会影响之前的状态,符合动态规划的应用条件。

三、本题的具体实现:

         首先我们肯定要定义出来状态

   定义状态
定义 dp[i][j] 表示处理到字符串第 i 个字符时,使用 j 次修改后能获得的最多不相交 "ovo" 子串数量。注意i要等于3(

  • "ovo" 是三个连续字符组成的子串,因此至少需要处理到第3个字符才能形成第一个可能的子串。
  • 例如字符串索引为 1-32-4 等,必须从i=3开始检查。

接着进行状态的更新:

将 dp[i][j] 初始化为 dp[i-1][j],表示不选择以 i 结尾的子串时的最优解。

java">for (int j = 0; j <= k; j++) {dp[i][j] = dp[i-1][j];
}

尝试更新状态
检查能否以 i 结尾形成一个 "ovo" 子串:

  • 计算代价 cost:将 i-2, i-1, i 修改为 "ovo" 所需的操作次数。
  • 状态转移:若当前剩余操作次数 j ≥ cost,则比较继承值和选择当前子串后的值,取最大。

仅当 j ≥ cost 时,允许转移

java">for (int j = cost; j <= k; j++) {dp[i][j] = Math.max(dp[i][j], dp[i-3][j-cost] + 1);
}

   计算修改代价:

java">int cost = 0;
if (str.charAt(i-2) != 'o') cost++; // 第一个字符需是o
if (str.charAt(i-1) != 'v') cost++; // 第二个字符需是v
if (str.charAt(i) != 'o') cost++;   // 第三个字符需是o

不断更新最大值:

java">ans = Math.max(ans, dp[i][j]); // 记录所有可能的最大值

四、完整代码实现:

java">import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int T = sc.nextInt();while (T-- > 0) {int n = sc.nextInt();int k = sc.nextInt();String str = " " + sc.next(); // 转换为1-based索引int[][] dp = new int[n+1][k+1];int ans = 0;for (int i = 3; i <= n; i++) {// 继承i-1位置的状态for (int j = 0; j <= k; j++) {dp[i][j] = dp[i-1][j];}// 计算将i-2,i-1,i三个字符变为vov的代价int cost = 0;if (str.charAt(i-2) != 'o') cost++;if (str.charAt(i-1) != 'v') cost++;if (str.charAt(i) != 'o') cost++;// 状态转移:消耗cost次操作,数量+1for (int j = cost; j <= k; j++) {dp[i][j] = Math.max(dp[i][j], dp[i-3][j-cost] + 1);ans = Math.max(ans, dp[i][j]);}}System.out.println(ans);}}
}
要点:
  • 状态设计:二维数组跟踪位置和修改次数。
  • 转移逻辑:分不选/选当前子串两种情况,确保不重叠。
  • 边界处理:从 i=3 开始,避免越界。
  • 复杂度:时间复杂度 O(nk),空间复杂度 O(nk)

总结

以上就是今天要讲的内容,动态规划通过状态定义和转移方程,系统地穷举所有可能,确保在修改次数限制和子串不重叠的约束下找到最优解。理解每一步的状态变化和转移条件是解题的核心。这还只是毛毛雨,我感觉理解这个过程是最重要的,希望大家都能不断学习和进步。


http://www.ppmy.cn/devtools/166899.html

相关文章

前端知识点---http.createHttp()的理解(arkts)

通俗易懂的例子&#xff1a;点外卖 &#x1f354;&#x1f964; 想象一下&#xff0c;你在家里点外卖&#xff0c;HTTP 请求就像是你和餐厅之间的沟通方式。 1️⃣ 没有 http.createHttp()&#xff1a;每次点餐都重新拨电话 &#x1f4de; 如果你每次点餐都重新拨打餐厅的电话…

python之数据处理的安全(链家)

一、模块设计思路与核心价值 # 代码核心安全处理逻辑 element soup.select_one(css_selector) if element else default_value设计目标&#xff1a;构建具备自愈能力的爬虫系统&#xff0c;应对网页改版、反爬策略、网络抖动等复杂场景 核心价值&#xff1a; 数据完整性保障…

智能对话小程序功能优化day1-登录鉴权

目录 1.数据库表构建。 2.完善登录相关的实例对象。 3.登录相关功能实现。 4.小程序效果。 最近尝试下trae加入claude3.7后的读图生成代码功能&#xff0c;可以看到简单的页面一次性生成确实准确率高了不少&#xff0c;想起来之前笔记中开发的智能问答小程序功能还是有些简…

小程序 wxml 语法 —— 39 简单双向数据绑定

在 WXML 中&#xff0c;普通属性的绑定是单向的&#xff0c;比如 <input value"{{ value }}" />&#xff0c;当数据发生改变时&#xff0c;页面也会随之发生变化&#xff0c;但是当用户在输入框中输入最新内容&#xff0c;最新内容并不会同步给 value 数据&…

【实战ES】实战 Elasticsearch:快速上手与深度实践-5.3.2实时配送范围计算(距离排序+多边形过滤)

&#x1f449; 点击关注不迷路 &#x1f449; 点击关注不迷路 &#x1f449; 点击关注不迷路 文章大纲 5.3.2 实时配送范围计算深度实践&#xff1a;距离排序多边形过滤1. 核心需求与挑战1.1 业务场景参数1.2 性能基准要求 2. 混合索引架构设计2.1 双索引联合方案2.2 分片策略优…

多线程--参数传递之间的关系

在C中创建线程时&#xff0c;传递参数的方式会影响参数的生命周期、线程的安全性和性能。以下是几种常见的传递方式及其适用情况&#xff1a; 1. 值传递 值传递会创建参数的副本&#xff0c;并在线程函数内部使用该副本。这种方式可以避免线程之间的竞态条件&#xff0c;因为…

QT系列教程(16) 定时器事件

定时器 Qt中提供了两种方式实现定时器&#xff0c;第一种是通过startTimer的方式启动定时器&#xff0c;该函数返回定时器的id&#xff0c;然后我们需要为实现定时器的类重写timerEvent。我们先介绍这一种&#xff0c;创建Qt Application项目&#xff0c;项目默认的类名为Widg…

python编写的一个打砖块小游戏

游戏介绍 打砖块是一款经典的街机游戏&#xff0c;玩家控制底部的挡板&#xff0c;使球反弹以击碎上方的砖块。当球击中砖块时&#xff0c;砖块消失&#xff0c;球反弹&#xff1b;若球碰到挡板&#xff0c;则改变方向继续运动&#xff1b;若球掉出屏幕底部&#xff0c;玩家失…