TopCoder SRM 573, Division 2, Level 1 : SkiResortsEasy

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12469&rd=15493

概要

あるスキー場には、N 箇所の "場所" があり、各場所は一直線上に繋がれている。
スキーは、高さが等しいか、より低い場所にのみ移動できる。
各場所の高さを低くする操作ができ、高さを 1 低くするためのコストが 1 である。
各場所の高さの情報が与えられるので、場所 0 から場所 N - 1 まで移動できるようにするのに必要なコストの最小値を求めよ。

解法

出発地点から順に、その時点での最高点の高さをもちながら、飛び出す分を答えとして加算していきます。
具体的に述べると、次のようになります。
最高点の高さの初期値を出発地点の高さとして、以降の場所に於いては

• その場所の高さが最高点の高さより高い → 二つの値の差を答えに加算
• それ以外 → 最高点の高さを、その場所の高さに更新する

コード

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

class SkiResortsEasy
{
public:
	int minCost( vector <int> altitude )
	{
		const int N = altitude.size();
		int height = altitude[0], res = 0;
		REP( i, 1, N )
		{
			if ( height < altitude[i] )
			{
				res += altitude[i] - height;
			}
			else
			{
				height = altitude[i];
			}
		}
		return res;
	}
};