問題概要
初めに正整数の多重集合 $a$ がある.$|a| > 1$ である間,以下の操作をする.
- $a$ から要素を 2 つ取り除き,それらを $x, y$ とする.
- $a$ に $x + y$ を加える
- $xy$ のスコアを得る
得られる累計スコアの最大値を求めよ.
$2 \leq |a| \leq 100$
解法
$|a| = N$ とします.
Division 1, Level 1 の類題です.マージの手順も Div1 Edition での分割と同様に二分木で表すことができます.また,最終的なスコアは初期状態のみに依存して,マージの手順には依存しないことも分かります.$a$ による最終スコアは $\sum_{ i = 0 }^{ N - 1 } a_i = s$ として,$$\frac{ \sum_{ i = 0 }^{ N - 1 }a_i( s - a_i ) }{ 2 }$$ となります.
$a$ の総和を求めるのに $O( N )$ 時間,スコアの計算にも $O( N )$ 時間かかるので,全体でも $O( N )$ 時間です.
コード
#define ALL( c ) begin( c ), end( c ) class CombiningSlimes { public: int maxMascots( vector <int> a ) { const int sum = accumulate( ALL( a ), 0 ); transform( ALL( a ), begin( a ), [=]( const int s ){ return s * ( sum - s ); } ); return accumulate( ALL( a ), 0 ) / 2; } };