SRM499 Div1 Medium

550

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

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

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

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

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

view plainprint?

1. class WhiteSpaceEditing {  
2. public:  
3.   int getMinimum(vector <int> v)  
4.   {  
5.     v.insert(v.begin(), 0);  
6.     const int N = v.size();  
7.   
8.     int sum = N - 2;  
9.     for (int i = 0; i < N; ++i) {  
10.       sum += max(v[i] - v[i - 1], 0);  
11.     }  
12.   
13.     return sum;  
14.   }  
15. };  

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;
  }
};