TopCoder SRM 559 Div2 Easy BlockTower

この回は不参加。
あとでチャレンジしたけど、このDiv2 Easyは何気にSystem Testで初回ミスっていた。

http://community.topcoder.com/stat?c=problem_statement&pm=12200

この問題、数列が与えられるのでその部分数列を抜き出し、和を最大にするもの。
ただし、奇数の後に偶数は取れない。

この問題は１回奇数をとるとあとは奇数しか取れない。
よって、前半は偶数、後半は奇数をとるようにして、奇数を取り始める場所を変えて試せばよい。
Editorialもほぼ同じ回答だね。

class BlockTower {
	public:
	int getTallest(vector <int> blockHeights) {
		int msum,sum;
		int i,j;
		
		msum=0;
		FOR(i,blockHeights.size()+1) {
			sum=0;
			FOR(j,blockHeights.size()) {
				int h=blockHeights[j];
				if(j<i && ((h%2)==0)) sum+=h;
				if(j>=i && ((h%2)==1)) sum+=h;
			}
			msum=max(sum,msum);
		}
		return msum;
		
	}
};

まとめ

簡単ではあるけど、こういう問題は割と好き。