torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 585, Division 2, Level 1 : LISNumberDivTwo

概要

数列が与えられる。
この数列が最小でいくつの狭義単調増加列に分割されるか求めよ。

解法

隣接する要素が狭義単調増加でないとき、必ずその場所で分割する必要があります。
それ以外の場合分割する必要はありません。
従って、全ての隣り合う二要素について、狭義単調増加でないようなものの数が答えになります。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class LISNumberDivTwo
{
public:
	int calculate( vector <int> seq )
	{
		int res = 1;
		REP( i, 0, seq.size() - 1 )
		{
			res += seq[i] >= seq[ i + 1 ];
		}
		return res;
	}
};