P1969积木大赛

YTC

https://www.luogu.org/problemnew/show/P1969

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

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

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

输入输出格式
输入格式：
包含两行，第一行包含一个整数 n ，表示大厦的宽度。

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

输出格式：
建造所需的最少操作数。

输入输出样例
输入样例#1：
5
2 3 4 1 2
输出样例#1：
5

YTC

1. #include<iostream>
   
2. using namespace std;
   
3. int n,h,maxh;
   
4. long long ans;
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     for(int i=1;i<=n;i++)
   
9.     {
   
10.         cin>>h;
    
11.         if(h>maxh)
    
12.         {
    
13.             ans+=h-maxh;//如果后面的大于当前目标，显然要多搞几次才行，，，
    
14. //如果小于，现在在搞这一块的时候顺便就可以把下一块弄好了
    
15. //所以只要+下一块比现在多的就可以了
    
16.             maxh=h;//更新现在目标的值
    
17.         }
    
18.         else maxh=h;//更新现在目标的值
    
19.     }
    
20.     cout<<ans;
    
21.     return 0;
    
22. }
    
23. //根据贪心的思路，这样的策略次数最少

复制代码

直接模拟会T

Scorpio

1. #include<iostream>
   
2. using namespace std;
   
3. int h[105000];
   
4. int i,k,n;
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     for(i=1;i<=n;i++)
   
9.     {
   
10.         cin>>h[i];
    
11.         if(h[i]>h[i-1])
    
12.             k=k+(h[i]-h[i-1]);
    
13.     }
    
14.     cout<<k;
    
15.     return 0;
    
16. }

复制代码