読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

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

TopCoder SRM 596, Division 2, Level 1 : FoxAndSightseeing

概要

数列 a が与えれ、先頭・末尾以外の要素を一つ削除することができる。
削除後における、
 \sum_{i = 0}^{ size(a) - 1 }{ | a_{i+1} - a_i | }
の最小値を求めよ。

解法

要素の削除を全通り試して最小値を計算します。

コード

typedef vector<int> VI;

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

class FoxAndSightseeing
{
public:
	int getMin( vector <int> position )
	{
		const int N = position.size();
		
		int res = INT_MAX;
		REP( i, 1, N - 1 )
		{
			VI ps( position );
			ps.erase( ps.begin() + i );

			int d = 0;
			REP( i, 0, ps.size() - 1 )
			{
				d += abs( ps[ i + 1 ] - ps[i] );
			}
			res = min( res, d );
		}

		return res;
	}
};