SRM559 Div2 Easy BlockTower
問題
ブロックがN個あり、
そのブロックには0からN-1のインデックスが割り当てられている。
また、それぞれのブロックの高さが分かっている。
ブロックを積み上げてタワーを作りたいのだが、
下記のようなルールがある。
1. ブロックはインデックスがより大きくなるように積み上げなくてはならない。
(数字はインデックス) 6 6 5 4 3 1 1 3 0 2 OK NG
2. 高さが奇数のブロックの上に、高さが偶数のブロックを載せてはならない。
(数字は高さ) 4 1 2 2 3 6 8 7 7 2 2 2 4 4 4 OK OK NG
タワーが最も高くなるようにブロックを積み上げた時の、その高さを返せ。
制約
1 <= ブロックの数 <= 50
1 <= ブロックの高さ <= 50
方針
高さ奇数のブロックを使った瞬間、
その後の高さ偶数のブロックは全く使えなくなる。
インデックス順にループを回していって
高さ奇数のブロックが出てきたら
そのブロックを使った時のタワーの高さを計算し最大値をとっていく。
最後に高さ偶数のブロックのみを使った時のタワーの高さとの最大値をとる。
ソースコード
class BlockTower { public: int getTallest(vector <int> blockHeights){ int n = blockHeights.size(); int res = 0; int total = 0; // 高さ偶数のブロックを使ったタワーの高さ for( int i = 0; i < n; i++ ){ int h = blockHeights[i]; if( h % 2 == 0 ){ // 偶数 total += h; }else{ // 奇数 int t = total; for( int j = i; j < n; j++ ){ int h2 = blockHeights[j]; if( h2 % 2 != 0 ){ t += h2; } } res = max( res, t ); } } res = max( res, total ); return res; } };