华师一附中OI组

标题: P1969积木大赛 [打印本页]
作者: YTC    时间: 2018-6-5 17:04
标题: P1969积木大赛
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    时间: 2018-6-13 12:59
  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    时间: 2018-6-23 09:43
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2