# ABC116 C - Grand Garden

# 概要

最初に高さ00の花がNN本ある。 今, このNN本の花の高さをh[i]h[i]にしたい. 「水やり」の操作が以下のように定義される時, 最小の水やりの回数を求めよ.

# 解法

まず制約を確認すると, NNhih_iも最大値が10210^2なので, O(N4)O(N^4)程度までループで間に合いそうなことが分かる.

テストケースを手でごにょごにょすると, 12211 2 2 1のように単調増加・単調減少の数字列に関して, その最大値を減じれば良いことが分かる.

ただし, 単調増加・単調減少を調べるのも良いが, 制約が緩いので両端が00であるような部分列に対して11ずつ減じていけば良いことが分かる.

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n; cin>>n;
  vector<int> h(n);
  for(int i=0;i<n;++i) cin>>h[i];
  
  int ans=0;
  // [l, r)の区間は全て正
  for(int l=0;l<n;++l){
    while(h[l]>0){
      int r;
      for(r=l+1;r<n;++r){
        if(h[r]==0)break;
      }
      
      // ここで閉じている左端もついでに引いておく
      for(int i=l;i<r;++i){
        --h[i];
      }
      ++ans;
    }
  }
  cout << ans << endl;
  return 0;
}

# 参考資料

Last Updated: 2019-3-14 02:04:59