SRM533 Div1 Easy

250
順に取り除いていくのではなく、挿入していくことを考える。
そうすれば、挿入位置の左右にうまく分割して考えられる。
memo[左端][右端] = 間のどれかを挿入したときの最大値

取り除いていってもDPになりそうにないなー =>> あれ？何か皆やたら提出が早い =>> 貪欲か!?
結果、惨敗

const int N = 50 + 1;
int t[N][N];

vector<int> W;

int rec(int b, int e)
{
  if (t[b][e] != -1) return t[b][e];
  int mx = 0;
  for (int i = b + 1; i < e; ++i) {
    mx = max(mx, rec(b, i) + rec(i, e) + W[b] * W[e]);
  }
  return t[b][e] = mx;
}

class CasketOfStar {
public:
  int maxEnergy(vector <int> W_)
  {
    W = W_;
    fill(&t[0][0], &t[N - 1][N], -1);
    return rec(0, (int)W.size() - 1);
  }

};