目次

• 問題
  • 入力
  • 出力
  • 入出力例
• 解説
• 計算量
• 解答

# 問題

https://atcoder.jp/contests/arc006/tasks/arc006_3

# 入力

N
w_1
w_2
...
w_N

• N - ダンボールの個数（$1 \leq N \leq 50$）
• w_i - ダンボール$i$の重さ（$1 \leq w_i \leq 100000$）

# 出力

ダンボールを先頭から、新しい場所に配置するか、または既存の自身以上の重さをもつダンボールの上に配置する事ができます.
既存のダンボールの上に配置した時にはスペースを消費せず、新しい場所に配置した場合にのみスペースが消費されます.

この時必要な最小スペースを答える問題です.

# 入出力例

5
4
3
1
2
1

2

先頭からルールに従って配置していくと1の上に2は置けないのでそこで２つ目のスペースが消費されます.

1 |
3 | 1
4 | 2
-----
1 | 2

# 解説

ダンボールの順番を変えることが出来ないのでシンプルです.
新しいダンボールを配置するのは、 配置済みのダンボールの山の一番上を見ていって自身以上の重さをもつダンボールがあればその上に配置.
無ければ新しいスペースに配置する.
この２択だけです.
注意点はダンボールの山に自身以上の重さがあるダンボールが２つ以上ある時どれを選択すればよいかです.
より重いダンボールはより多くのダンボールを上に積める可能性のあるダンボールなので出来るだけ消費したくありません.
なので自身以上の重さのダンボールのうち一番軽いダンボールを選択するべきです.

実装は、少し工夫することでシンプルになります.
それぞれの山の一番上の重さだけを配列Bに保存します.
最初は配列は空です.
この配列を先頭から見ていって最初に見つかった自身以上の重さを自身で上書きします（B[i] = w）.
見つからない場合は配列の末尾に自身を追加します（B.add(w)）.
すべてのダンボールの配置が完了したら配列の長さB.size()が答えです.

最初に見つかったものを選んで良いのは、上に積めなかったものが末尾に追加されるのでより重いものほど後ろになるからです.
先頭の方が軽いのでより価値の低いものになります.

# 計算量

$O(N^2)$

# 解答

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define MAX_N 50
#define MAX_W 100000

Int N;
vector<Int> W;
vector<Int> B;

void input() {
  cin >> N;
  Int w_;
  while (cin >> w_) W.push_back(w_);
}

void solve() {
  loop(w,0,W.size()) {
    Int index = -1;
    loop(b,0,B.size()) {
      if (B.at(b) >= W.at(w)) {
        index = b;
        break;
      }
    }

    if (index < 0) B.push_back(W.at(w));
    else B[index] = W.at(w);
  }

  cout << B.size() << endl;
}

int main() {
  input();
  solve();
  return 0;
}