[AtCoder] ABC 116 C – Grand Garden

2019年5月11日

問題

方針

最適な水やりの方法

水やりの操作回数を最小化するには、連続した区間 \( [l, r ]\) が大きくなるように水をやる必要があります。つまり、連続して水やりをできる区間は一回の操作で高さを \( 1 \) 上げるというようにします。

最小回数の計算

左端から水やりを連続した区間に行うようにします。このとき、最低でも \(h_1 \) 回の操作が必要になります。次に隣の花の高さに注目します。

• \( h_1 < h_2 \) のとき

このとき、\(h_1 \) 回水やりをしたとしても、花 \( 2 \) の高さは \(h_1 \) となるので、さらに追加で \( h_2 – h_1 \) 回の操作が必要になります。

• \( h_1 > h_2 \) のとき

このとき、\( h_1 \) 回水やりを行う途中で、花 \( 2 \) の高さは \( h_2 \) となっています。したがって、途中で区間が途切れることになります。このとき、追加の操作は発生しないことに注意します。

上記を踏まえて、現在水やりを行ってできる最大の高さは一つ前の花の高さになります。また、操作回数の初期値は \( h_1 \) となり、\( i = 2 \) から調べることになります。

• \( h_i < h_{i +1}\) のとき

このとき、操作回数に \(h_{i+1} – h_i \) を追加します。

• \( h_i \geq h_{i + 1} \)

このとき、操作回数の変化はありません。

コード

提出したコード

コストの計算

int cost = h[0];
  for (int i = 1; i < N; i++) {
    if (h[i - 1] < h[i]) {
      cost += h[i] - h[i - 1];
    } 
  }

上記のように計算ができます。