1264: 积木大赛

朱雀 2024-02-18 22:04 80阅读 0赞

### **1264: 积木大赛** ###

时间限制: 1 Sec 内存限制: 128 MB  
提交: 58 解决: 35  
您该题的状态：**已完成**  
\[[提交][Link 1]\]\[[状态][Link 2]\]\[[讨论版][Link 3]\]

### **题目描述** ###

春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦，大厦可以看成由n块宽度为1的积木组成，第i块积木的最终高度需要是hi。

在搭建开始之前，没有任何积木（可以看成n块高度为0的积木）。接下来每次操作，小朋友们可以选择一段连续区间\[L, R\]，然后将第L块到第R块之间（含第L块和第R块）所有积木的高度分别增加1。

小M是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。

### **输入** ###

每组输入数据包含两行，第一行包含一个整数n，表示大厦的宽度。

第二行包含n个整数，第i个整数为hi。

数据规模：

其中一种可行的最佳方案，依次选择 \[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。

### **输出** ###

每组输出仅一行，即建造所需的最少操作数。

下面是对样例数据的解释：

其中一种可行的最佳方案，依次选择

\[1, 5\] \[1, 3\] \[2, 3\] \[3, 3\] \[5, 5\]

### **样例输入** ###

<span style="color:#333333"><span style="color:black">5</span></span>

\#include<iostream>  
using namespace std;  
int sum,n;  
int a\[100010\]=\{0\};  
int main()  
\{  
int i,j,m;  
while(~scanf("%d",&n))  
\{  
sum=0;  
  
for(i=1;i<=n;i++)  
\{  
cin>>a\[i\];  
if(a\[i\]>a\[i-1\])  
sum+=a\[i\]-a\[i-1\];  
\}  
cout<<sum<<endl;  
\}  
return 0;  
\}

还有更简单的，不用数组，省的爆内存。

`#include<cstdio>`

`using` `namespace` `std;`

`int` `n,i,a=0,b,ans=0;`

`int` `main()`

`{`

```scanf``(``"%d"``,&n);`

```for``(i=1;i<=n;i++)`

```{`

```scanf``(``"%d"``,&b);`

```if``(a<b)ans+=(b-a);`

```a=b;`

```}`

```printf``(``"%d"``,ans);`

```return` `0;`

`}`

[Link 1]: http://xyoj.xynu.edu.cn/submitpage.php?id=1264
[Link 2]: http://xyoj.xynu.edu.cn/problemstatus.php?id=1264
[Link 3]: http://xyoj.xynu.edu.cn/bbs.php?pid=1264

发表评论取消回复

表情：

评论列表（有 0 条评论，80人围观）

还没有评论，来说两句吧...

相关阅读

相关 1264: 积木大赛

1264: 积木大赛时间限制: 1 Sec 内存限制: 128 MB 提交: 58 解决: 35 您该题的状态：已完成 \[[提交][Link 1]\]\[

朱雀/ 2024年02月18日 22:04/ 0 赞/ 81 阅读

相关 nod1264 线段相交（计算几何）

1264 线段相交基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题收藏关注给出平面上两条线段的两个端点，判断这两条线段是否相交（有一

迈不过友情╰/ 2024年02月17日 23:17/ 0 赞/ 91 阅读

相关 HDU - 1264 （暴力模拟）

题目：[https://cn.vjudge.net/problem/HDU-1264][https_cn.vjudge.net_problem_HDU-1264] 思路：直接

水深无声/ 2023年08月17日 16:26/ 0 赞/ 141 阅读

相关 P1969-积木大赛

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

￡神魔★判官ぃ/ 2023年06月01日 08:52/ 0 赞/ 10 阅读

相关 Medium之1264.页面推荐

朋友关系列表： Friendship <table> <thead> <tr> <th>Column Name</th> <th>Type</th>

ゝ一纸荒年。/ 2022年08月30日 01:54/ 0 赞/ 151 阅读

相关 UESTC 1264-人民币的构造

人民币的构造 [Edit][] Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (J

ゞ浴缸里的玫瑰/ 2022年08月19日 13:20/ 0 赞/ 224 阅读

相关【基础练习】【贪心】【递推】NOIP2013提高组第五题积木大赛题解

还是先把题目放上吧：春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦，大厦可以看成由n块宽度为1的积木组成，第n块积木的最终高度需要是hi。

约定不等于承诺〃/ 2022年08月07日 09:41/ 0 赞/ 308 阅读

相关堆积木

题目描述： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9n

朴灿烈づ我的快乐病毒、/ 2022年03月11日 07:38/ 0 赞/ 174 阅读

相关 51Nod 1264：线段相交（计算几何）

51Nod 1264：线段相交 Decision 给出平面上两条线段的两个端点，判断这两条线段是否相交（有一个公共点或有部分重合认为相交）。如果相交，输出"Yes

痛定思痛。/ 2021年12月21日 03:35/ 0 赞/ 282 阅读

相关 noip2013——提高组——积木大赛

noip2013 D2T1 太简单了，不说了。 include<iostream> include<cstdio> include<algorith

男娘i/ 2021年12月11日 11:49/ 0 赞/ 265 阅读