SRM 669 Div2 Medium CombiningSlimes

問題

SRM 669 - TopCoder Wiki

複数のスライムが与えられた時に,任意の2個のスライムを合体させ,スライムの個数が1つになるまで繰り返す. 各スライムはサイズが与えられ,サイズx, yのスライムを合体させると,x+yのスライムが出来,x*yのスコアを得る. 得ることが出来る最大のスコアを求める問題.

解答

  • よく分からなかったので,各ステップで最小のサイズと最大のサイズを選ぶ戦略をとって提出してみた
  • 解説を見ると,どんなやり方でもスコアが同じになるらしい.
class CombiningSlimes
{
public:
  int maxMascots(vector <int> a)
    {
      int res = 0;
      while(a.size() > 1){
        sort(a.begin(), a.end());
        res += a[0] * a[a.size()-1];
        int merged = a[0] + a[a.size()-1];
        a.erase(a.begin() + a.size()-1);
        a[0] = merged;
      }
      return res;
    }
};