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

kmjp's blog

競技プログラミング参加記です

TopCoder SRM 573 Div2 Easy SkiResortsEasy

さて、Div2も練習。
Div1 Mediumを簡単にした感じ。
http://community.topcoder.com/stat?c=problem_statement&pm=12469

問題

N個のポイントからなるスキー場で、各ポイントの高さが数値の配列で与えられる。
ポイント0からポイント(N-1)に順に移動する際、移動先は移動元と同じか低くないといけない。
各ポイントは、コスト1で高さを1下げれるとき、ポイント(N-1)に到達するまでの最小コストを答える。

解法

移動先の方が高ければ、移動元と同じ高さになるまで下げればよい。

class SkiResortsEasy {
	public:
	int minCost(vector <int> altitude) {
		int ta=0;
		int i;
		int CA=altitude[0];
		
		for(i=1;i<altitude.size();i++) {
			if(altitude[i]>CA) ta += altitude[i]-CA;
			else CA=altitude[i];
		}
		return ta;
	}
};

まとめ

Div2 Easyということで流石に簡単。

広告を非表示にする