洛谷—— P1969 积木大赛
2024-08-31 13:15:07
https://www.luogu.org/problem/show?pid=1969
题目描述
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦,大厦可以看成由n块宽度为1的积木组成,第i块积木的最终高度需要是hi。
在搭建开始之前,没有任何积木(可以看成n块高度为 0 的积木)。接下来每次操作,小朋友们可以选择一段连续区间[l, r],然后将第第 L 块到第 R 块之间(含第 L 块和第 R 块)所有积木的高度分别增加1。
小 M 是个聪明的小朋友,她很快想出了建造大厦的最佳策略,使得建造所需的操作次数最少。但她不是一个勤于动手的孩子,所以想请你帮忙实现这个策略,并求出最少的操作次数。
输入输出格式
输入格式:
输入文件为 block.in
输入包含两行,第一行包含一个整数n,表示大厦的宽度。
第二行包含n个整数,第i个整数为hi 。
输出格式:
输出文件为 block.out
仅一行,即建造所需的最少操作数。
输入输出样例
输入样例#1:
5
2 3 4 1 2
输出样例#1:
5
说明
【样例解释】
其中一种可行的最佳方案,依次选择
[1,5] [1,3] [2,3] [3,3] [5,5]
【数据范围】
对于 30%的数据,有1 ≤ n ≤ 10;
对于 70%的数据,有1 ≤ n ≤ 1000;
对于 100%的数据,有1 ≤ n ≤ 100000,0 ≤ hi≤ 10000。
求出差分序列,查分结果>0的和就是答案
#include <cstdio> using namespace std; int n,x,pre,ans,ch; inline void read(int &x)
{
ch=getchar();x=;
for(;ch<''||ch>'';ch=getchar()) continue;
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-'';
} int main()
{
read(n);
for(int i=;i<=n;i++)
{
read(x);
if((x-pre)>) ans+=x-pre;
pre=x;
}
printf("%d",ans);
return ;
}
最新文章
- Collection
- UIAlertController、UIAlertAction 警告框
- lr常用
- 线性布局通过适配器可以动态加载view
- sass安装 使用
- 如何在XAF中显示自定义窗体和控件
- 问题-";Record not found or changed by another user";
- 利用setTimeOut 和clearTimeOut 方法控制写一个 滑动导航显示不同信息的效果
- MyEclipse安装xfire插件
- Contains Duplicate leetcode
- Spring Boot 2.0(二):Spring Boot 2.0尝鲜-动态 Banner
- 写XML
- DCGAN 代码简单解读
- Linux学习之文件系统权限及表示
- Qt websocket
- you&#39;ve successfully authenticated, but Gitee.com does not provide she access.
- hive函数--编码解码
- Confluence 6 附件存储配置
- wpf项目打开多个窗体在任务栏只有一个任务
- HTML中的锚点设置和table格式
热门文章
- mysql忘记密码怎么处理
- redhat 7 cenos 7 网络配置文件
- UT源码+105032014018
- 洛谷 P2040 打开所有的灯
- hadoop-07-ntp服务检查
- h5 离线存储
- bzoj3158&;3275: 千钧一发(最小割)
- bzoj2438: [中山市选2011]杀人游戏(强联通+特判)
- What is the difference between SET and SELECT when assigning values to variables, in T-SQL?
- zzulioj--1828-- 贪心的小猫咪(贪心模拟)