当前位置: 首页 > news >正文

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≤rmax​ai​). 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

InputcopyOutputcopy
8 3
5 4 2 6 5 1 9 2
20
3 2 3

Sample 2

InputcopyOutputcopy
5 1
1 1 1 1 1
1
5

Sample 3

InputcopyOutputcopy
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 开发中&#xff0c;一个重要的组成部分便是数据库了。Web 程序中最常用的莫过于关系型数据库了&#xff0c;也称 SQL 数据库。另外&#xff0c;文档数据库&#xff08;如 mongodb&#xff09;、键值对数据库&#xff08;如 redis&#xff09;近几年也逐渐在 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))

装饰器模式 装饰器模式是一种结构型设计模式&#xff0c;用于动态地给对象添加额外的行为或责任&#xff0c;而不需要改变原始对象的结构。通过创建一个包装器类&#xff08;装饰器&#xff09;&#xff0c;它包含原始对象的引用&#xff0c;并提供与原始对象相同的接口&#…...

小程序v-for与key值使用

小程序中的v-for和key与Vue中的用法基本相同。v-for用于循环渲染列表&#xff0c;key用于给每个循环项分配一个唯一的标识。 使用v-for时&#xff0c;通常建议使用wx:for代替&#xff0c;例如&#xff1a; <view wx:for"{{ items }}" wx:key"id">{…...

Qt包含文件不存在问题解决 QNetworkAccessManager

这里用到了Qt的网络模块&#xff0c;在.pro中添加了 QT network 但是添加 #include <QNetworkAccessManager> 会报错说找不到&#xff0c;可以通过在项目上右键执行qmake后&#xff0c;直接#include <QNetworkAccessManager>就不会报错了&#xff1a;...

【视频图像篇】FastStone Capture屏幕长截图软件

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

【C语言】每日一题(杨氏矩阵查找数)

目录 杨氏矩阵介绍&#xff1a;方法&#xff1a;思路&#xff1a;代码实现&#xff1a; 杨氏矩阵介绍&#xff1a; 既然在杨氏矩阵中查找数&#xff0c;那什么是杨氏矩阵呢&#xff1f; 矩阵的每行从左到右是递增的&#xff0c;矩阵从上到下是递增的。 例如&#xff1a; 方法…...

探究SpringWeb对于请求的处理过程

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

如何使用Google Compute Engine入门指南快速创建和配置您的云虚拟机实例

文章目录 步骤1&#xff1a;创建 Google Cloud Platform&#xff08;GCP&#xff09;账户步骤2&#xff1a;设置 GCP 项目步骤3&#xff1a;启用 Google Compute Engine API步骤4&#xff1a;安装 Google Cloud SDK步骤5&#xff1a;创建虚拟机实例步骤6&#xff1a;连接到虚拟…...

springMVC中全局异常处理

前言&#xff1a; 当不同方法执行时&#xff0c;抛出相同异常。为了简约代码和避免重复使用try{}catch{}。此时使用统一异常处理。但局部的统一异常处理只能为所在类所调用。因此产生全局异常处理&#xff0c;该类中统一异常处理方法可以作用于整个controller。&#xff08;以…...

【Nginx24】Nginx学习:压缩模块Gzip

Nginx学习&#xff1a;压缩模块Gzip 又是一个非常常见的模块&#xff0c;Gzip 现在也是事实上的 Web 应用压缩标准了。随便打开一个网站&#xff0c;在请求的响应头中都会看到 Content-Encoding: gzip 这样的内容&#xff0c;这就表明当前这个请求的页面或资源使用了 Gzip 压缩…...

我的私人笔记(zookeeper分布式安装)

分布式安装 1.安装前准备 (1)下载zookeeper&#xff1a;Index of /dist/zookeeper&#xff08;当前使用为3.4.10版本&#xff09; (2)安装JDK (3)拷贝zookeeper安装包到Linux系统下 (4)解压到指定目录 tar -xzvf zookeeper-3.4.10.tar.gz -C /opt/servers/ (5)修改名称 …...

小程序排名优化全攻略

随着小程序的快速发展,小程序之间的竞争也日益激烈。如何在竞争对手众多的环境下脱颖而出,通过小程序排名优化来提高曝光率和流量转化率,已成为许多小程序开发者和运营者关注的重点。本文将全面解析小程序排名优化的方法,让您可以更好地提升小程序的搜索排名。 【名即微】 小程…...

MySQL MHA

什么是 MHA MHA&#xff08;Master High Availability&#xff09;是一套优秀的MySQL高可用环境下故障切换和主从复制的软件 MHA 的出现就是解决MySQL 单点故障的问题 MySQL故障切换过程中&#xff0c;MHA能做到0-30秒内自动完成故障切换操作 MHA能在故障切换的过程中最大程度上…...

Java API速记手册(持续更新ing...)

诸神缄默不语-个人CSDN博文目录 之所以干这个事原因也很简单&#xff0c;因为我3年没写Java了&#xff0c;现在在复健。 因为我最近都在用Python&#xff0c;所以跟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 作者&#xff1a;马海峰 *&#xff0c;陆克 * †&#xff0c;薛健 *&#xff0c;牛泽海 *&#xff0c;高鹏程† * 中国科学院大学工程学院&#xff0c;北京100049 鹏程实验室&#xff0c;深圳518055 来源&#xff1a;202…...

数据结构零基础入门篇(C语言实现)

前言&#xff1a;数据结构属于C学习中较难的一部分&#xff0c;对应学习者的要求较高&#xff0c;如基础不扎实&#xff0c;建议着重学习C语言中的指针和结构体&#xff0c;万丈高楼平地起。 目录&#xff1a; 一&#xff0c;链表 1&#xff09;单链表的大致结构实现 2&…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...