SRM499 Div1 Medium

550

DPを疑った後で諦めて貪欲へ。

小さいケースとサンプルを手で試す限りでは DELETE 無しでも答えが合う。
SPACE と相殺するから？

**
****
******
#####
###
#
作る順番に制約がないので、* 側を作る途中で RETURN して # 側を作っても構わないはず。

*******
*****
***
**
*****
*******
こう凹みがあったとしても、凹んだ部分で分割すれば山になる。

増加にだけ着目してしまえば良さそう。300 とか 450 くらいの問題にも思える。
どうやら、DP 解がちゃんとあるらしい。

class WhiteSpaceEditing {
public:
  int getMinimum(vector <int> v)
  {
    v.insert(v.begin(), 0);
    const int N = v.size();

    int sum = N - 2;
    for (int i = 0; i < N; ++i) {
      sum += max(v[i] - v[i - 1], 0);
    }

    return sum;
  }
};