【蓝桥杯集训·每日一题】AcWing 3662. 最大上升子序列和

article/2024/7/17 3:15:49

文章目录

  • 一、题目
    • 1、原题链接
    • 2、题目描述
  • 二、解题报告
    • 1、思路分析
    • 2、时间复杂度
    • 3、代码详解
  • 三、知识风暴
  • 树状数组

一、题目

1、原题链接

3662. 最大上升子序列和

2、题目描述

给定一个长度为 n 的整数序列 a1,a2,…,an。

请你选出一个该序列的严格上升子序列,要求所选子序列的各元素之和尽可能大

请问这个 最大值是多少

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

输出最大的上升子序列和。

数据范围

对于前三个测试点,1≤n≤4
对于全部测试点,1≤n≤105,1≤ai≤109

输入样例1

2
100 40

输出样例1

100

输入样例2

4
1 9 7 10

输出样例2

20

样例解释*

对于样例 1,我们只选取 100。

对于样例 2,我们选取 1,9,10。

二、解题报告

1、思路分析

思路来源:y总讲解视频
y总yyds

(1)dp[i]表示所有以a[i]结尾的的所有上升子序列中序列和的最大值。

  • a[i]前面的一个数为是原序列第几个元素(或者没有)对dp[i]进行分类。
  • a[i]前面一个数为a[k](k>=1&&k<i&&a[k]<a[i]),由于最后一个数固定是a[i],所以我们要求该子序列和的最大值,只要保证前面以a[k]结尾的子序列的和最大即可。即转移方程为 dp[i]=max(dp[i],dp[k]+a[i])

(2)如果不进行dp优化,时间复杂度最坏为O(n2),会超时。所以需要利用离散化先将序列中的数映射到一个数组中去,这样就转化成了求所有小于a[i]的所有前缀的最大值,利用树状数组进行优化,最终将时间复杂度控制在O(nlogn)。

2、时间复杂度

时间复杂度为O(nlogn)

3、代码详解

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=100010;
LL tr[N];   //树状数组
int a[N],q[N];   //q[]为离散化数组
int n,m;
//返回最低位的一位1
int lowbit(int x){return x&-x;
}
//添加、更新tr[],存储以x结尾的子序列最大和
void add(int x,LL v){for(int i=x;i<=m;i+=lowbit(i)){tr[i]=max(tr[i],v);}
}
//查询1~x的前缀的最大值
LL query(int x){LL ans=0;for(int i=x;i;i-=lowbit(i)){ans=max(ans,tr[i]);}return ans;
}
int main(){cin>>n;for(int i=0;i<n;i++) cin>>a[i];//离散化memcpy(q,a,sizeof a);sort(q,q+n);m=unique(q,q+n)-q;LL ans=0;for(int i=0;i<n;i++){int x=lower_bound(q,q+m,a[i])-q+1;   //二分离散化后的值LL sum=query(x-1)+a[i];ans=max(ans,sum);add(x,sum);}cout<<ans;return 0;
}

三、知识风暴

树状数组


http://www.ngui.cc/article/show-1007655.html

相关文章

Oracle 启动后一会儿就挂掉故障处理—ORA-600 17182----惜分飞

一例正常运行的数据库突然节点不停重启(因为是rac,启动一会儿就crash,然后又被crs给启动起来,然后有crash,依次循环),告警日志类似:Fri Mar 24 13:36:07 2023QMNC started with pid124, OS id188397 ARC3: Archival startedARC0: STARTING ARCH PROCESSES COMPLETECompleted: A…

JNI原理及常用方法概述

1.1 JNI(Java Native Interface) 提供一种Java字节码调用C/C的解决方案&#xff0c;JNI描述的是一种技术。 1.2 NDK(Native Development Kit) Android NDK 是一组允许您将 C 或 C&#xff08;“原生代码”&#xff09;嵌入到 Android 应用中的工具&#xff0c;NDK描述的是工具集…

【PC自动化测试-3】GUI对象检查工具

1&#xff0c;Inspect.exe (C:\Program Files(x86)\Windows Kits\10\bin\x64)Inspect.exe 是Microsoft创建的另外一个很棒的工具。它包含在Windows SDK中&#xff0c;因此可以在x64 Windows上的一下位置找到它上传资源https://download.csdn.net/download/qq_26086231/87530399…

Golang流媒体实战之二:回源

欢迎访问我的GitHub 这里分类和汇总了欣宸的全部原创(含配套源码)&#xff1a;https://github.com/zq2599/blog_demos 本篇概览 今天的实战是流传输过程中的常见功能&#xff1a;回源如下图&#xff0c;lal(源站)和lal(拉流节点)代表两台电脑&#xff0c;上面都部署了lalVLC在…

面试官:vue2和vue3的区别有哪些

目录 多根节点&#xff0c;fragment&#xff08;碎片&#xff09; Composition API reactive 函数是用来创建响应式对象 Ref toRef toRefs 去除了管道 v-model的prop 和 event 默认名称会更改 vue2写法 Vue 3写法 vue3组件需要使用v-model时的写法 其他语法 1. 创…

Android SDK对应版本

前言 很多时候看到某个版本都无法对应起来&#xff0c;需要去网上查找&#xff0c;这里做个记录&#xff0c;方便查找对应版本。 平台版本SDK版本版本名称13.0T(33)Android 13 (Android Tiramisu)12LSv2(32)Android 12L (Android Sv2)12.0S(31)Android 12 (Android S)11.0R(3…

图解WebView -- (1) WebView概述

前言 目前各移动应用或多或少都内嵌了Web网页&#xff0c;在Android开发中&#xff0c;就不可避免的使用本系列的主角——WebView。 一、WebView 是什么&#xff1f; WebView是Android 展示Web网页的控件&#xff0c;类似于应用提供一个内置的浏览器&#xff0c;在应用内实现…

【Mongoose笔记】SOCKS5 服务器

【Mongoose笔记】socks5 服务器 简介 Mongoose 笔记系列用于记录学习 Mongoose 的一些内容。 Mongoose 是一个 C/C 的网络库。它为 TCP、UDP、HTTP、WebSocket、MQTT 实现了事件驱动的、非阻塞的 API。 项目地址&#xff1a; https://github.com/cesanta/mongoose学习 下…

重启Android后SystemProperties属性变化

重启Android后SystemProperties属性变化1、SystemProperties属性加载2、PropertySet条件限制3、SystemProperties属性变化android12-release1、SystemProperties属性加载 查看 SystemProperties属性加载 属性映射区域LoadPath("/dev/__properties__/property_info")…

CentOs7 + Stable Diffusion + Novel AI实现AI绘画

前提条件 GPU服务器含有NVIDIA显卡安装Git环境&#xff08;版本 > 1.8.5&#xff09; 查看版本&#xff1a;git version 升级git&#xff1a;yum install -y https://repo.ius.io/ius-release-el7.rpm && yum install -y epel-release && yum erase -y git…