[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

相关文章

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

沁恒CH32在MounRiver Studio上环境配置以及使用详细教程

目录 1.  RISC-V简介 2.  CPU架构现状 3.  MounRiver Studio软件下载 4.  MounRiver Studio软件安装 5.  MounRiver Studio软件介绍 6.  创建工程 7.  编译代码 1.  RISC-V简介         RISC就是精简指令集计算机(Reduced Instruction SetCom

MiniGPT-3D, 首个高效的3D点云大语言模型,仅需一张RTX3090显卡,训练一天时间,已开源

项目主页:https://tangyuan96.github.io/minigpt_3d_project_page/ 代码:https://github.com/TangYuan96/MiniGPT-3D 论文:https://arxiv.org/pdf/2405.01413 MiniGPT-3D在多个任务上取得了SoTA,被ACM MM2024接收,只拥有47.8M的可训练参数,在一张RTX

arduino ide安装详细步骤

​ 大家好,我是程序员小羊! 前言: Arduino IDE 是一个专为编程 Arduino 微控制器设计的集成开发环境,使用起来非常方便。下面将介绍如何在不同平台上安装 Arduino IDE 的详细步骤,包括 Windows、Mac 和 Linux 系统。 一、在 Windows 上安装 Arduino IDE 1. 下载 Arduino IDE 打开 Arduino 官网

GPT系列之:GPT-1,GPT-2,GPT-3详细解读

一、GPT1 论文:Improving Language Understanding by Generative Pre-Training 链接:https://cdn.openai.com/research-covers/languageunsupervised/language_understanding_paper.pdf 启发点:生成loss和微调loss同时作用,让下游任务来适应预训

Spark MLlib模型训练—聚类算法 PIC(Power Iteration Clustering)

Spark MLlib模型训练—聚类算法 PIC(Power Iteration Clustering) Power Iteration Clustering (PIC) 是一种基于图的聚类算法,用于在大规模数据集上进行高效的社区检测。PIC 算法的核心思想是通过迭代图的幂运算来发现数据中的潜在簇。该算法适用于处理大规模图数据,特别是在社交网络分析、推荐系统和生物信息学等领域具有广泛应用。Spa

STL经典案例(四)——实验室预约综合管理系统(项目涉及知识点很全面,内容有点多,耐心看完会有收获的!)

项目干货满满,内容有点过多,看起来可能会有点卡。系统提示读完超过俩小时,建议分多篇发布,我觉得分篇就不完整了,失去了这个项目的灵魂 一、需求分析 高校实验室预约管理系统包括三种不同身份:管理员、实验室教师、学生 管理员:给学生和实验室教师创建账号并分发 实验室教师:审核学生的预约申请 学生:申请使用实验室 高校实验室包括:超景深实验室(可容纳10人)、大数据实验室(可容纳20人)、物联网实验

多路转接之select(fd_set介绍,参数详细介绍),实现非阻塞式网络通信

目录 多路转接之select 引入 介绍 fd_set 函数原型 nfds readfds / writefds / exceptfds readfds  总结  fd_set操作接口  timeout timevalue 结构体 传入值 返回值 代码 注意点 -- 调用函数 select的参数填充  获取新连接 注意点 -- 通信时的调用函数 添加新fd到

SigLIP——采用sigmoid损失的图文预训练方式

SigLIP——采用sigmoid损失的图文预训练方式 FesianXu 20240825 at Wechat Search Team 前言 CLIP中的infoNCE损失是一种对比性损失,在SigLIP这个工作中,作者提出采用非对比性的sigmoid损失,能够更高效地进行图文预训练,本文进行介绍。如有谬误请见谅并联系指出,本文遵守CC 4.0 BY-SA版权协议,转载请联系作者并注