新闻详情

新闻详情

首页 / 资讯中心 / 详情

C++之线性DP

发布时间:2026/11/21 14:33:16来源:尧图网络
C++之线性DP
引言线性dp用来解决线性一维最大/最小问题可以降低时间复杂度先看题描述八戒押 x 两银子猫掌柜给定一个乱序数组 arr长度为 N有正数也有负数正数表示赢钱负数表示输钱。求 arr 的一个连续子数组使得子数组的和最大这样八戒才能尽可能的赢钱。这个和最大的子数组叫做最大子段和。输入描述第一行有两个数字分别是 x 和 N用空格隔开。第二行有 N 个数字用空格隔开表示数组元素。输出描述输出八戒最多赢多少钱若八戒想即时止损则输出一个负数表示八戒最少输多少钱。样例输入 112 8 1 -2 3 10 -4 7 2 -5样例输出 16提示1≤x,N≤100000最大子数组为[3 10 -4 7 2]和为18八戒押了12两银子所以最后赢6两分析这道题如果没学过线性dp第一眼看上去会很茫然。其实这是一道经典问题——最大子段和。那么问题来了总不能把所有子段枚举一遍吧聪明的你想到了这种方法dp[1] arr[1]; for (int i 1; i n; i) { if (dp[i - 1] 0) { dp[i] arr[i]; } else { dp[i] arr[i] dp[i - 1]; } max_s max(max_s, dp[i]); } cout max_s;恭喜你发明了最大子段和算法。再看一道题描述一个数的序列 bi​当 b1​b2​...bS​ 的时候我们称这个序列是上升的。对于给定的一个序列 (a1​,a2​,...,aN​)我们可以得到一些上升的子序列 (ai1​​, ai2​​, …, aiK​​)这里 1≤i1​i2​...iK​≤N。比如对于序列(1,7,3,5,9,4,8)有它的一些上升子序列如(1,7),(3,4,8)等等。这些子序列中和最大为 18为子序列(1,3,5,9)的和。你的任务就是对于给定的序列求出最大上升子序列和。注意最长的上升子序列的和不一定是最大的比如序列 (100,1,2,3) 的最大上升子序列和为 100而最长上升子序列为 (1,2,3)。输入描述输入的第一行是序列的长度 N(1≤N≤1000)。第二行给出序列中的 N 个整数这些整数的取值范围都在 0 到 10000(可能重复)。输出描述最大上升子序列和。样例输入 17 111111 7 3 5 9 4 11111样例输出 1111111提示1≤N≤1000分析这题和上一题差不多都求最大和这里就直接上代码了#include bits/stdc.h using namespace std; int n, dp[1009], a[1009], ans; int main() { cin n; for (int i 1; i n; i) { cin a[i]; dp[i] a[i]; } for (int i 2; i n; i) { for (int j 1; j i; j) { if (a[i] a[j]) { dp[i] max(dp[i], a[i] dp[j]); } } } for (int i 1; i n; i) { ans max(ans, dp[i]); } cout ans; return 0; }再来一道题描述一个数的序列 bi​当 b1​b2​...bS​ 的时候我们称这个序列是上升的。对于给定的一个序列 (a1​,a2​,...,aN​)我们可以得到一些上升的子序列(ai1​,ai2​,...,aiK​)这里1≤i1​,1≤i2​,...,1≤ik​≤N.比如对于序列 (1,7,3,5,9,4,8)有它的一些上升子序列如(1,7),(3,4,8)等等。这些子序列中最长的长度是4比如子序列(1,3,5,8)。你的任务就是对于给定的序列求出最长上升子序列的长度。输入描述输入的第一行是序列的长度 N(1≤N≤1000)。第二行给出序列中的 N 个整数这些整数的取值范围都在 0 到 10000。输出描述最长上升子序列的长度。样例输入 17 1 7 3 5 9 4 8样例输出 14分析这题和上一题的唯一区别就在于求长度or和稍微改一下代码就行了第八行初始化改为dp[i] 1;第13行改为dp[i] max(dp[i], dp[j] 1);小结线性dp往往是解决实际问题的基础学好线性dp竞赛中才能尽可能少出现TLE的问题
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/21 14:14:45

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/21 14:14:26

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/20 20:45:42

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/20 16:11:20

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/20 18:41:01

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/21 14:13:11

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉