[Algorithm][综合训练][体育课测验(二)][合唱队形][宵暗的妖怪]详细讲解

本文主要是介绍[Algorithm][综合训练][体育课测验(二)][合唱队形][宵暗的妖怪]详细讲解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 1.体育课测验(二)
    • 1.题目链接
    • 2.算法原理详解 && 代码实现
  • 2.合唱队形
    • 1.题目链接
    • 2.算法原理详解 && 代码实现
  • 3.宵暗的妖怪
  • 1.题目链接
    • 2.算法原理详解 && 代码实现


1.体育课测验(二)

1.题目链接

  • 体育课测验(二)

2.算法原理详解 && 代码实现

  • 说明:单纯积累一题[拓扑排序]用于加强印象
    • 能识别模型,并且写出代码
     vector<int> findOrder(int n, vector<vector<int> >& groups) {vector<vector<int>> edges(n);vector<int> in(n);// 1.建图for(auto v : groups){int a = v[0], b = v[1]; // b -> aedges[b].push_back(a);in[a]++;}// 2.入度为0的点,加入到队列中queue<int> q;for(int i = 0; i < n; i++){if(in[i] == 0){q.push(i);}}// 3.拓扑排序vector<int> ret;while(q.size()){int tmp = q.front();q.pop();ret.push_back(tmp);for(auto x : edges[tmp]){if(--in[x] == 0){q.push(x);}}}if(ret.size() == n){return ret;}else{return {};}}
    

2.合唱队形

1.题目链接

  • 合唱队形

2.算法原理详解 && 代码实现

  • 问题转化:依次枚举任意位置的同学,将其作为山峰位置,找出最长的x + y - 1
    请添加图片描述

  • 解法:动态规划 -> 最长递增子序列模型

    • 状态表示dp[i]:以i位置为结尾的所有子序列中,最长上升子序列的长度
      • f[i]:以i位置同学为结尾的最长上升子序列的长度
      • g[i]:以i位置同学为结尾的最长上升子序列的长度(从后向前看)
    • 状态转移方程
      请添加图片描述
    #include <iostream>
    #include <vector>
    using namespace std;int main()
    {int n = 0;cin >> n;vector<int> nums(n, 0), f(n, 1), g(n, 1);for(auto& x : nums){cin >> x;}// 从前向后for(int i = 0; i < n; i++){for(int j = 0; j < i; j++){if(nums[j] < nums[i]){f[i] = max(f[i], f[j] + 1);}}}// 从后向前for(int i = n - 1; i >= 0; i--){for(int j = i + 1; j < n; j++){if(nums[i] > nums[j]){g[i] = max(g[i], g[j] + 1);}}}int len = 0;for(int i = 0; i < n; i++){len = max(len, f[i] + g[i] - 1);}cout << n - len << endl;return 0;
    }
    

3.宵暗的妖怪

1.题目链接

  • 宵暗的妖怪

2.算法原理详解 && 代码实现

  • 解法:动态规划 --> 线性DP
    • 状态表示dp[i]:从[1, n]区间内吞噬黑暗,最大的饱食度是多少

    • 状态转移方程
      请添加图片描述

    • 初始化
      请添加图片描述

    • 返回值dp[n]

    #include <iostream>
    #include <vector>
    using namespace std;int main()
    {int n = 0;cin >> n;vector<long long> nums(n + 1, 0), dp(n + 1, 0);for(int i = 1; i <= n; i++){cin >> nums[i];}for(int i = 3; i <= n; i++){dp[i] = max(dp[i - 1], dp[i - 3] + nums[i - 1]);}cout << dp[n] << endl;return 0;
    }
    

这篇关于[Algorithm][综合训练][体育课测验(二)][合唱队形][宵暗的妖怪]详细讲解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1126789

相关文章

Python对接支付宝支付之使用AliPay实现的详细操作指南

《Python对接支付宝支付之使用AliPay实现的详细操作指南》支付宝没有提供PythonSDK,但是强大的github就有提供python-alipay-sdk,封装里很多复杂操作,使用这个我们就... 目录一、引言二、准备工作2.1 支付宝开放平台入驻与应用创建2.2 密钥生成与配置2.3 安装ali

2025版mysql8.0.41 winx64 手动安装详细教程

《2025版mysql8.0.41winx64手动安装详细教程》本文指导Windows系统下MySQL安装配置,包含解压、设置环境变量、my.ini配置、初始化密码获取、服务安装与手动启动等步骤,... 目录一、下载安装包二、配置环境变量三、安装配置四、启动 mysql 服务,修改密码一、下载安装包安装地

RabbitMQ消费端单线程与多线程案例讲解

《RabbitMQ消费端单线程与多线程案例讲解》文章解析RabbitMQ消费端单线程与多线程处理机制,说明concurrency控制消费者数量,max-concurrency控制最大线程数,prefe... 目录 一、基础概念详细解释:举个例子:✅ 单消费者 + 单线程消费❌ 单消费者 + 多线程消费❌ 多

在macOS上安装jenv管理JDK版本的详细步骤

《在macOS上安装jenv管理JDK版本的详细步骤》jEnv是一个命令行工具,正如它的官网所宣称的那样,它是来让你忘记怎么配置JAVA_HOME环境变量的神队友,:本文主要介绍在macOS上安装... 目录前言安装 jenv添加 JDK 版本到 jenv切换 JDK 版本总结前言China编程在开发 Java

Spring Boot Actuator应用监控与管理的详细步骤

《SpringBootActuator应用监控与管理的详细步骤》SpringBootActuator是SpringBoot的监控工具,提供健康检查、性能指标、日志管理等核心功能,支持自定义和扩展端... 目录一、 Spring Boot Actuator 概述二、 集成 Spring Boot Actuat

如何在Java Spring实现异步执行(详细篇)

《如何在JavaSpring实现异步执行(详细篇)》Spring框架通过@Async、Executor等实现异步执行,提升系统性能与响应速度,支持自定义线程池管理并发,本文给大家介绍如何在Sprin... 目录前言1. 使用 @Async 实现异步执行1.1 启用异步执行支持1.2 创建异步方法1.3 调用

Spring Boot 与微服务入门实战详细总结

《SpringBoot与微服务入门实战详细总结》本文讲解SpringBoot框架的核心特性如快速构建、自动配置、零XML与微服务架构的定义、演进及优缺点,涵盖开发环境准备和HelloWorld实战... 目录一、Spring Boot 核心概述二、微服务架构详解1. 微服务的定义与演进2. 微服务的优缺点三

SpringBoot改造MCP服务器的详细说明(StreamableHTTP 类型)

《SpringBoot改造MCP服务器的详细说明(StreamableHTTP类型)》本文介绍了SpringBoot如何实现MCPStreamableHTTP服务器,并且使用CherryStudio... 目录SpringBoot改造MCP服务器(StreamableHTTP)1 项目说明2 使用说明2.1

从入门到进阶讲解Python自动化Playwright实战指南

《从入门到进阶讲解Python自动化Playwright实战指南》Playwright是针对Python语言的纯自动化工具,它可以通过单个API自动执行Chromium,Firefox和WebKit... 目录Playwright 简介核心优势安装步骤观点与案例结合Playwright 核心功能从零开始学习

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java