企业发展历程网站,wordpress中文文章排版插件,网站开发 怎么才能发表情,长春网站建设电话题干#xff1a;
题目描述
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为nn的大厦#xff0c;大厦可以看成由n块宽度为1的积木组成#xff0c;第i块积木的最终高度需要是h_ihi。
在搭建开始之前#xff0c;没有任何积木#xff08;可以看…题干
题目描述
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为nn的大厦大厦可以看成由n块宽度为1的积木组成第i块积木的最终高度需要是h_ihi。
在搭建开始之前没有任何积木可以看成nn块高度为00的积木。接下来每次操作小朋友们可以选择一段连续区间[l, r][l,r]然后将第第LL块到第 RR 块之间含第LL 块和第 RR块所有积木的高度分别增加11。
小MM是个聪明的小朋友她很快想出了建造大厦的最佳策略使得建造所需的操作次数最少。但她不是一个勤于动手的孩子所以想请你帮忙实现这个策略并求出最少的操作次数。
输入输出格式
输入格式 包含两行第一行包含一个整数nn表示大厦的宽度。
第二行包含nn个整数第i个整数为h_ihi。 输出格式 建造所需的最少操作数。 输入输出样例
输入样例#1 复制
5
2 3 4 1 2
输出样例#1 复制
5
说明
【样例解释】
其中一种可行的最佳方案依次选择
[1,5][1,5] [1,3][1,3] [2,3][2,3] [3,3][3,3] [5,5][5,5]
【数据范围】
对于30\%30%的数据有1 ≤ n ≤ 101≤n≤10
对于 70\%70%的数据有1 ≤ n ≤ 10001≤n≤1000
对于 100\%100%的数据有1 ≤ n ≤ 100000,0 ≤ h_i≤ 100001≤n≤100000,0≤hi≤10000。 NOIP2018 铺设道路 (road.cpp/c/pas) 【问题描述】 春春是一名道路工程师负责铺设一条长度为 n 的道路。 铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块首尾相连的区 域一开始第 i 块区域下陷的深度为 d i 。 春春每天可以选择一段连续区间 [L,R] 填充这段区间中的每块区域让其下陷深 度减少 1。在选择区间时需要保证区间内的每块区域在填充前下陷深度均不为 0 。 春春希望你能帮他设计一种方案可以在最短的时间内将整段道路的下陷深度都变 为 0 。 【输入格式】 输入文件名为 road.in 。 输入文件包含两行第一行包含一个整数 n表示道路的长度。 第二行包含 n 个整数相邻两数间用一个空格隔开第 i 个整数为 d i 。 【输出格式】 输出文件名为 road.out 。 输出文件仅包含一个整数即最少需要多少天才能完成任务。 【输入输出样例 1】 road.in road.out 6 4 3 2 5 3 5 9
解题报告 这两者是一样的题在此以积木大赛作为讲解。 首先你如果暴力的话会重复算很多次然后你发现相邻两者如果高度有个递增的关系的话是可以省去第二次的运算的但是如果高度是递减的那就需要更新高度重新算了看代码不难理解了。。思路也不是很难想。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
int a[MAX];
int main()
{int n;int cnt 0,cur 0;cinn;for(int i 1; in; i) scanf(%d,ai);for(int i 1; in; i) {if(a[i] cur) cnt (a[i] - cur); cur a[i];}printf(%d\n,cnt);return 0 ;}