ARC006 C - 積み重ね
解法
貪欲解で解くひとが多いと思うので,それ以外の解法を.
この問題は,よく考えると「与えられたDAGの最小パス被覆を求めよ」と言い換えられる.
実際,x が y の上に積める,を y -> x という有向辺として表現すれば,DAGができる.
DAGの最小パス被覆は,頂点数からDAGを2部グラフと見たときの最大マッチングの数を引いたものである.
しかし,圧倒的に貪欲のほうが楽ではある.(自分はパット見てマッチングに帰着させてしまったけど.)
ソースコード
#include <bits/stdc++.h> using namespace std; using graph = std::vector<std::vector<int>>; // bipartite_matching は略. int main() { int N; cin >> N; vector<int> w(N); for(int i = 0; i < N; ++i) { cin >> w[i]; } graph g(N*2); for(int i = 0; i < N; ++i) { for(int j = i + 1; j < N; ++j) { if(w[i] >= w[j]) { g[i].push_back(j + N); } } } cout << N - bipartite_matching(g) << endl; }