SRM527 Div1 Easy

275
メモ化する。
memo[まだ使ってない頂点][片側だけ使っている辺][どちらも空いている辺]

const int D = 52;
int t[D][D][D];

int rec(int v, int e, int h, const vector<int> &S)
{
  if (v == 0 && e == 0 && h == 0) {
    return 0;
  }
  if (v == 0) return -(1 << 20);

  if (t[v][e][h] != -1) {
    return t[v][e][h];
  }

  int mx = -(1 << 20);

  for (int i = 0; i <= e; ++i) {
    for (int j = 0; j <= h; ++j) {
      if (h + i - j < 0) continue;
      if (i + j && i + j <= (int)S.size()) {
        mx = max(mx, rec(v - 1, e - i, h + i - j, S) + S[i + j - 1]);
      }
    }
  }

  return t[v][e][h] = mx;
}

class P8XGraphBuilder {
public:
  int solve(vector <int> S)
  {
    fill(&t[0][0][0], &t[D-1][D-1][D], -1);
    return rec(S.size() + 1, S.size(), 0, S);
  }
};