B - Polycarp‘s Practice
Polycarp is practicing his problem solving skill. He has a list of nn problems with difficulties a_1, a_2, \dots, a_na1,a2,…,an, respectively. His plan is to practice for exactly kk days. Each day he has to solve at least one problem from his list. Polycarp solves the problems in the order they are given in his list, he cannot skip any problem from his list. He has to solve all nn problems in exactly kk days.
Thus, each day Polycarp solves a contiguous sequence of (consecutive) problems from the start of the list. He can't skip problems or solve them multiple times. As a result, in kk days he will solve all the nn problems.
The profit of the jj-th day of Polycarp's practice is the maximum among all the difficulties of problems Polycarp solves during the jj-th day (i.e. if he solves problems with indices from ll to rr during a day, then the profit of the day is \max\limits_{l \le i \le r}a_il≤i≤rmaxai). The total profit of his practice is the sum of the profits over all kk days of his practice.
You want to help Polycarp to get the maximum possible total profit over all valid ways to solve problems. Your task is to distribute all nn problems between kk days satisfying the conditions above in such a way, that the total profit is maximum.
For example, if n = 8, k = 3n=8,k=3 and a = [5, 4, 2, 6, 5, 1, 9, 2]a=[5,4,2,6,5,1,9,2], one of the possible distributions with maximum total profit is: [5, 4, 2], [6, 5], [1, 9, 2][5,4,2],[6,5],[1,9,2]. Here the total profit equals 5 + 6 + 9 = 205+6+9=20.
Input
The first line of the input contains two integers nn and kk (1 \le k \le n \le 20001≤k≤n≤2000) — the number of problems and the number of days, respectively.
The second line of the input contains nn integers a_1, a_2, \dots, a_na1,a2,…,an (1 \le a_i \le 20001≤ai≤2000) — difficulties of problems in Polycarp's list, in the order they are placed in the list (i.e. in the order Polycarp will solve them).
Output
In the first line of the output print the maximum possible total profit.
In the second line print exactly kk positive integers t_1, t_2, \dots, t_kt1,t2,…,tk (t_1 + t_2 + \dots + t_kt1+t2+⋯+tk must equal nn), where t_jtj means the number of problems Polycarp will solve during the jj-th day in order to achieve the maximum possible total profit of his practice.
If there are many possible answers, you may print any of them.
Sample 1
Inputcopy | Outputcopy |
---|---|
8 3 5 4 2 6 5 1 9 2 | 20 3 2 3 |
Sample 2
Inputcopy | Outputcopy |
---|---|
5 1 1 1 1 1 1 | 1 5 |
Sample 3
Inputcopy | Outputcopy |
---|---|
4 2 1 2000 2000 2 | 4000 2 2 |
Note
The first example is described in the problem statement.
In the second example there is only one possible distribution.
In the third example the best answer is to distribute problems in the following way: [1, 2000], [2000, 2][1,2000],[2000,2]. The total profit of this distribution is 2000 + 2000 = 40002000+2000=4000.
题目翻译
给定长度为n的序列,要求分成k段,最大化每段最大值的和
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<string.h>
#include<climits>
#include<map>
#include<algorithm>
typedef long long ll;
using namespace std;
const int N = 2010;
int n, k;struct node {int num, val;
}mm[N];bool cmp1(node n1, node n2)
{return n1.val > n2.val;
}bool cmp2(node n1, node n2)
{return n1.num < n2.num;
}int main()
{cin >> n >> k;for (int i = 1; i <= n; i++){int num;cin >> num;mm[i].num = i;mm[i].val = num;}sort(mm + 1, mm + n + 1, cmp1);//先对整个序列按照数值的大小进行排序,去前k个数的和int sum = 0;for (int i = 1; i <= k; i++) sum += mm[i].val;sort(mm + 1, mm + k + 1, cmp2); //在对前k个数进行排序,做差分组cout << sum << endl;for (int i = 1; i < k; i++) cout << mm[i].num - mm[i - 1]. num << " ";cout << n - mm[k - 1].num << endl;return 0;
}
相关文章:
B - Polycarp‘s Practice
Polycarp is practicing his problem solving skill. He has a list of nn problems with difficulties a_1, a_2, \dots, a_na1,a2,…,an, respectively. His plan is to practice for exactly kk days. Each day he has to solve at least one problem from his list. …...
朴素贝叶斯数据分类------
------------------后期会编辑些关于朴素贝叶斯算法的推导及代码分析----------------- import numpy as np import pandas as pd from sklearn.model_selection import train_test_split from sklearn.naive_bayes import GaussianNB, BernoulliNB, MultinomialNB from sklear…...

flask中的操作数据库的插件Flask-SQLAlchemy
1、ORM 框架 Web 开发中,一个重要的组成部分便是数据库了。Web 程序中最常用的莫过于关系型数据库了,也称 SQL 数据库。另外,文档数据库(如 mongodb)、键值对数据库(如 redis)近几年也逐渐在 w…...
arrow的使用
pandas2.0引入了pyarrow作为可选后端,比numpy的性能提高很多,所以为了改造backtrader,用cython和c++重写整个框架,准备用arrow作为底层的数据结构(backtrader现在的底层数据结构是基于python array构建的) 安装arrow推荐使用vcpkg git clone https://github.com/Microsoft…...
【24种设计模式】装饰器模式(Decorator Pattern(Wrapper))
装饰器模式 装饰器模式是一种结构型设计模式,用于动态地给对象添加额外的行为或责任,而不需要改变原始对象的结构。通过创建一个包装器类(装饰器),它包含原始对象的引用,并提供与原始对象相同的接口&#…...
小程序v-for与key值使用
小程序中的v-for和key与Vue中的用法基本相同。v-for用于循环渲染列表,key用于给每个循环项分配一个唯一的标识。 使用v-for时,通常建议使用wx:for代替,例如: <view wx:for"{{ items }}" wx:key"id">{…...

Qt包含文件不存在问题解决 QNetworkAccessManager
这里用到了Qt的网络模块,在.pro中添加了 QT network 但是添加 #include <QNetworkAccessManager> 会报错说找不到,可以通过在项目上右键执行qmake后,直接#include <QNetworkAccessManager>就不会报错了:...

【视频图像篇】FastStone Capture屏幕长截图软件
【视频图像篇】FastStone Capture屏幕长截图软件 FastStone Capture最常用的一款屏幕长截图软件—【蘇小沐】 文章目录 【视频图像篇】FastStone Capture屏幕长截图软件实验环境1、启动界面2、自定义工具栏3、自动保存 (一)长截图1、捕获滚动窗口2、捕获…...

【C语言】每日一题(杨氏矩阵查找数)
目录 杨氏矩阵介绍:方法:思路:代码实现: 杨氏矩阵介绍: 既然在杨氏矩阵中查找数,那什么是杨氏矩阵呢? 矩阵的每行从左到右是递增的,矩阵从上到下是递增的。 例如: 方法…...

探究SpringWeb对于请求的处理过程
探究目的 在路径归一化被提出后,越来越多的未授权漏洞被爆出,而这些未授权多半跟spring自身对路由分发的处理机制有关。今天就来探究一下到底spring处理了什么导致了才导致鉴权被绕过这样严重的问题。 DispatcherServlet介绍 首先在分析spring对请求处…...

如何使用Google Compute Engine入门指南快速创建和配置您的云虚拟机实例
文章目录 步骤1:创建 Google Cloud Platform(GCP)账户步骤2:设置 GCP 项目步骤3:启用 Google Compute Engine API步骤4:安装 Google Cloud SDK步骤5:创建虚拟机实例步骤6:连接到虚拟…...
springMVC中全局异常处理
前言: 当不同方法执行时,抛出相同异常。为了简约代码和避免重复使用try{}catch{}。此时使用统一异常处理。但局部的统一异常处理只能为所在类所调用。因此产生全局异常处理,该类中统一异常处理方法可以作用于整个controller。(以…...

【Nginx24】Nginx学习:压缩模块Gzip
Nginx学习:压缩模块Gzip 又是一个非常常见的模块,Gzip 现在也是事实上的 Web 应用压缩标准了。随便打开一个网站,在请求的响应头中都会看到 Content-Encoding: gzip 这样的内容,这就表明当前这个请求的页面或资源使用了 Gzip 压缩…...
我的私人笔记(zookeeper分布式安装)
分布式安装 1.安装前准备 (1)下载zookeeper:Index of /dist/zookeeper(当前使用为3.4.10版本) (2)安装JDK (3)拷贝zookeeper安装包到Linux系统下 (4)解压到指定目录 tar -xzvf zookeeper-3.4.10.tar.gz -C /opt/servers/ (5)修改名称 …...

小程序排名优化全攻略
随着小程序的快速发展,小程序之间的竞争也日益激烈。如何在竞争对手众多的环境下脱颖而出,通过小程序排名优化来提高曝光率和流量转化率,已成为许多小程序开发者和运营者关注的重点。本文将全面解析小程序排名优化的方法,让您可以更好地提升小程序的搜索排名。 【名即微】 小程…...
MySQL MHA
什么是 MHA MHA(Master High Availability)是一套优秀的MySQL高可用环境下故障切换和主从复制的软件 MHA 的出现就是解决MySQL 单点故障的问题 MySQL故障切换过程中,MHA能做到0-30秒内自动完成故障切换操作 MHA能在故障切换的过程中最大程度上…...
Java API速记手册(持续更新ing...)
诸神缄默不语-个人CSDN博文目录 之所以干这个事原因也很简单,因为我3年没写Java了,现在在复健。 因为我最近都在用Python,所以跟Python一样的部分我就不写了。 最基本的框架public class MainClass {public static void main(String[] args…...

FANUC机器人电气控制柜内部硬件电路和模块详细介绍
FANUC机器人电气控制柜内部硬件电路和模块详细介绍 PSU电源单元 通过背板传输了如下电源 +5 +2.0V +3.3 +24v +24E +15V -15V 主板--接口描述: 主板内部结构: 面板电路板: 引申一下 KM21 与 KM22 的作用它们分别接至操作面板上上的急停按...

LGFormer:LOCAL TO GLOBAL TRANSFORMER FOR VIDEO BASED 3D HUMAN POSE ESTIMATION
基于视频的三维人体姿态估计的局部到全局Transformer 作者:马海峰 *,陆克 * †,薛健 *,牛泽海 *,高鹏程† * 中国科学院大学工程学院,北京100049 鹏程实验室,深圳518055 来源:202…...

数据结构零基础入门篇(C语言实现)
前言:数据结构属于C学习中较难的一部分,对应学习者的要求较高,如基础不扎实,建议着重学习C语言中的指针和结构体,万丈高楼平地起。 目录: 一,链表 1)单链表的大致结构实现 2&…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...

Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
【WebSocket】SpringBoot项目中使用WebSocket
1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖,添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...