CasketOfStarEasy

問題

• CasketOfStarEasy
• 長さ n の数列x[i]が与えられる(インデックスは0, ..., n-1とする)。
• 以下の手順を数列の長さが2になるまで繰り返す。
  • 0 < i < n-1 なる i を選ぶ
  • x[i]は消える
  • この時、x[i-1] * x[i+1]が得点として加算される
• 最終的な得点が最大になる手順を探せ

方針

再帰で全探索。

コード

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


class CasketOfStarEasy{
public:
  int maxEnergy(vector <int> weight){
    return doit(weight);
  }
  int doit(vector<int> w){
    //copy(w.begin(), w.end(), ostream_iterator<int>(cout, ",")); cout << endl;
    if(w.size() == 2) return 0;
    int ret = 0;
    for(int i = 1; i < w.size()-1; i++){
      vector<int> x;
      for(int j = 0; j < w.size(); j++){
	if(j != i){
	  x.push_back(w[j]);
	}
      }
      ret = max(ret, w[i-1] * w[i+1] + doit(x));
    }
    return ret;
  }
};