提出しました。
ようやっと過去問を解きました。全通り計算してもそれほど時間はかからないので力技で解きます。
TopCoder Statistics - Problem Statement
問題文:
助手はブロック遊びが大好き。今、0からN-1番と名付けられたN個のブロックを持っている。それぞれのブロックの高さは正の整数である。より正確に言えば、それぞれのiについて高さはblockHeights[i]と表せる。助手は最大の高さになる積み方に興味を示した。いくつかルールがある。
- ブロックはひとつの棚に格納されている。タワーの高さは積んだブロックの総和である。
- ブロックのラベルは底から頂上に対して常に増えなければいけない。言い換えれば、いつでも助手はなんちゃらら。
(棚の左から順にブロックを積むこと。途中で入れ替えてはいけない)
- 奇数の高さの上に偶数の高さのブロックを置いてはいけない。
あなたはint型の配列blockHeightsが与えられる。最大の高さを答えなさい。
制約
- blockHeightsの配列の長さは1から50まで。
- それぞれのブロックの高さは1から50まで。
コード。
#include#include #include #include using namespace std; class BlockTower { public: int getTallest(vector bH){ int i,j,l,k=0,gsum=0,kisum=0,sum=0; vector g;vector gl; vector ki;vector kil; g.push_back(0);gl.push_back(-1); for(i=0;i kil.back()){ kisum=0; }else{ k=0; while(gl[j]>kil[k]) {k++;} for(;k array; for (i=0;i<10;++i){ array.push_back(a[i]); } for (i=0;i<10;++i){ printf("%d ",array[i]); } printf("\n"); ob1.getTallest(array); return 0; }
まずブロックを偶数と奇数のものに分ける。
またそのときの配列要素もそれぞれ別の配列に格納しておく。
(偶×n)+(奇×m)という風に積んでいくので、nを増やしていったりいろいろして考えるおわり。