競プロやります。

競プロを頑張るブログです。

AtCoder Beginner Contest 116:C - Grand Garden

https://atcoder.jp/contests/abc116/tasks/abc116_c
実装に時間がかかってしまいました。

方針

花の高さが最初  \{h\} で、これに水をかけることで高さを 0 にすると考えました。

水やりは連続した花にしか同時には行えないので、高さが 0 になった区間をまたぐ水やりはできません。そこで「高さが 1 以上の区間を出来るだけ広くとって、そこに水やりをする」という操作を繰り返します。

ソースコード

#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;
    while(true){
        // 区間の左端を求める。
        // h[i] != 0 になる最初の i が左端。
        int s = -1;
        for(int i=0; i<N; i++){
            if(h[i] != 0){
                s = i;
                break;
            }
        }
        // s = -1 のとき、全ての花の高さが 0 。
        if(s==-1) break;

        // 区間の右端を求める。
        // i = s から始めて、h[i] = 0 となる i の左隣が右端。
        // ただし h[N-1] が右端の場合もあるので注意する。
        int g = -1;
        for(int i=s; i<N; i++){
            if(h[i]==0){
                g = i-1;
                break;
            }
            if(i==N-1) g = N-1;
        }

        // 区間の中で最も低い花の分だけ、高さを低く出来る。
        int hmin = 101;
        for(int i=s; i<=g; i++){
            hmin = min(hmin, h[i]);
        }
        for(int i=s; i<=g; i++){
            h[i]-=hmin;
        }
        ans += hmin;
    }
    cout << ans << endl;
}