【做题笔记】P1969 积木大赛

非常感谢 rxz 大佬提供的思路。

首先放个图（rxz 画的）

采用贪心的策略：对于一个期望高度 \(h_i\) ，如果大于 \(h_{i-1}\)，那么最终答案要加上二者之差；如果小于或等于，那么说明在处理 \(h_{i-1}\) 时已经顺带处理了 \(h_i\) （可以这样想：每次处理以 \(h_i\) 的值开头最长一段最长单调递减字段）

注意：答案最小是 \(h_1\) （即，第一块积木最高），所以答案初始值为 \(h_1\)

#include <iostream>
#include <cstdio>

using namespace std;

int n,x,ans,now;

int main()
{
    cin>>n;
    cin>>x;
    now=x;
    ans=x;
    for(int i=2;i<=n;i++)
    {
        cin>>x;
        if(x>now)ans+=(x-now);
        now=x;
    }
    cout<<ans<<endl;
    return 0;
}

原文链接:https://www.cnblogs.com/Nicest1919/p/12308604.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有