CF 335 div.2-C/div.1-A/605A Sorting Railway Cars

タイトルリンク:http://codeforces.com/problemset/problem/605/A
1本の道路に1-n番のn台の车が任意の顺番で置いてあります.今、これらの车を升顺にソートします.移动するたびに1台の车を一番前か一番後ろに取り出すことができます.今、ソートを完了したい移动回数を闻きます.
解:1台1台取り出すのはすべて取るべきものを取り出すことに相当して、それから一定の順序でシーケンスの中に置くので、私达はまずすべて取るべきものを取り出して、それでは残って、きっと1列の連続的な上昇のシーケンスで、もし私达が移動する回数が最も少ないならば、それでは残ったこのシーケンスはきっと最も長いです.したがって,隣接数連続の最長上昇サブシーケンスを見つければよいだけで,このサブシーケンス長がkであると仮定すると,最小移動回数はn−kである.
この問題の難易度は移動の規則性を発見できることにあると思います.順番に取るのは一度に全部取り出すことに相当し、移動されない一定は連続的な上昇シーケンスを構成します.そして、欲張りでしょう.
コード:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int num[100005], len[100005];
int main()
{
	//freopen("input.txt", "r", stdin);
	int n, ans = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &num[i]);
	for (int i = 1; i <= n; ++i)
	{
		len[num[i]] = len[num[i] - 1] + 1;
	}
	for (int i = 1; i <= n; ++i)
		if (ans < len[i])
			ans = len[i];
	printf("%d
", n - ans);
	//system("pause");
	//while (1);
	return 0;
}