[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

相关文章

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析(结合应用场景)

《nginx-t、nginx-sstop和nginx-sreload命令的详细解析(结合应用场景)》本文解析Nginx的-t、-sstop、-sreload命令,分别用于配置语法检... 以下是关于 nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析,结合实际应

Spring boot整合dubbo+zookeeper的详细过程

《Springboot整合dubbo+zookeeper的详细过程》本文讲解SpringBoot整合Dubbo与Zookeeper实现API、Provider、Consumer模式,包含依赖配置、... 目录Spring boot整合dubbo+zookeeper1.创建父工程2.父工程引入依赖3.创建ap

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

创建Java keystore文件的完整指南及详细步骤

《创建Javakeystore文件的完整指南及详细步骤》本文详解Java中keystore的创建与配置,涵盖私钥管理、自签名与CA证书生成、SSL/TLS应用,强调安全存储及验证机制,确保通信加密和... 目录1. 秘密键(私钥)的理解与管理私钥的定义与重要性私钥的管理策略私钥的生成与存储2. 证书的创建与

使用Docker构建Python Flask程序的详细教程

《使用Docker构建PythonFlask程序的详细教程》在当今的软件开发领域,容器化技术正变得越来越流行,而Docker无疑是其中的佼佼者,本文我们就来聊聊如何使用Docker构建一个简单的Py... 目录引言一、准备工作二、创建 Flask 应用程序三、创建 dockerfile四、构建 Docker

Python设置Cookie永不超时的详细指南

《Python设置Cookie永不超时的详细指南》Cookie是一种存储在用户浏览器中的小型数据片段,用于记录用户的登录状态、偏好设置等信息,下面小编就来和大家详细讲讲Python如何设置Cookie... 目录一、Cookie的作用与重要性二、Cookie过期的原因三、实现Cookie永不超时的方法(一)

SpringBoot整合liteflow的详细过程

《SpringBoot整合liteflow的详细过程》:本文主要介绍SpringBoot整合liteflow的详细过程,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋...  liteflow 是什么? 能做什么?总之一句话:能帮你规范写代码逻辑 ,编排并解耦业务逻辑,代码

浏览器插件cursor实现自动注册、续杯的详细过程

《浏览器插件cursor实现自动注册、续杯的详细过程》Cursor简易注册助手脚本通过自动化邮箱填写和验证码获取流程,大大简化了Cursor的注册过程,它不仅提高了注册效率,还通过友好的用户界面和详细... 目录前言功能概述使用方法安装脚本使用流程邮箱输入页面验证码页面实战演示技术实现核心功能实现1. 随机

嵌入式数据库SQLite 3配置使用讲解

《嵌入式数据库SQLite3配置使用讲解》本文强调嵌入式项目中SQLite3数据库的重要性,因其零配置、轻量级、跨平台及事务处理特性,可保障数据溯源与责任明确,详细讲解安装配置、基础语法及SQLit... 目录0、惨痛教训1、SQLite3环境配置(1)、下载安装SQLite库(2)、解压下载的文件(3)、