【做题笔记】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;
}

巴特西

【做题笔记】P1969 积木大赛

最新文章

热门文章