SRM571 Div1 Medium

500
クリークなんて、どうせバックトラック。3 m >= 2 n の条件から、16個くらいの頂点を消すことを考える。

const int N = 50 + 1;
vector< pair<int, int> > e;
bool del[N];
vector<int> mp;

int rec(int depth, int size, int begin)
{
  int rem = size - depth;
  unless (rem * 3 >= size * 2) return -1;

  int mx = -(1 << 28);
  for (int i = begin; i < e.size(); ++i) {
    int a = e[i].first;
    int b = e[i].second;
    if (!del[a] && !del[b]) {

      del[a] = true;
      mx = max(mx, rec(depth + 1, size, i + 1));
      del[a] = false;

      del[b] = true;
      mx = max(mx, rec(depth + 1, size, i + 1));
      del[b] = false;

      break;
    }
  }
  if (mx < -1) {
    mx = 0;
    for (int i = 0; i < size; ++i) {
      unless (del[i]) mx += mp[i];
    }
  }
  return mx;
}

class MagicMolecule {
public:
  int maxMagicPower(vector <int> mp_, vector <string> g)
  {
    mp = mp_;
    e.clear();

    const int n = g.size();
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        if (g[i][j] == 'N') e.push_back(make_pair(i, j));
      }
    }

    fill(del, del + N, false);
    return rec(0, n, 0);
  }
};