SRM 533 Div2 Medium maxEnergy

問題

n個の星が並んでいる,各星は重さがあり,i番目の星を消滅させるとweight[i-1] * weight[i+1]のエネルギィを得ることが出来る.星を消滅させていき得られるエネルギィの最大量を求めよ.

解答

星の数が3〜10と少ないので,全ての消し方を考慮してもそれほど時間はかからない.愚直に全ての場合を計算し,その中で最大の値を求める.

class CasketOfStarEasy
{
public:
  int maxEnergy(vector <int> weight)
    {
      int n = weight.size();
      vector<int> pm;
      int i, j;
      int res = 0;
      for(i = 1; i < n-1; i++) pm.push_back(i);
      do {
        int total = 0;
        vector<bool> mask(n, true);
        for(i = 0; i < pm.size(); i++){
          int idx = pm[i];
          mask[idx] = false;
          int v = 1;
          for(j = idx-1; j >= 0; j--) if (mask[j]){
              v *= weight[j];
              break;
            }
          for(j = idx+1; j < n; j++) if (mask[j]){
              v *= weight[j];
              break;
            }
          // cout << "idx = " << idx << " v=" << v << endl;
          total += v;
        }
        // cout << total << endl;
        res = max(res, total);
      }while(next_permutation(pm.begin(), pm.end()));
      return res;
    }
};