POJ 2626 Chess

問題

チェス大会のチーム編成を考えたい。各チェスプレーヤについて、白チームとして戦った場合の強さと黒チームとして戦った場合の強さの2つが与えられる。30人以上のプレーヤの強さが与えられる。これらプレーヤから選抜で白チーム15人、黒チーム15人の編成を行うとき、強さの総和を最大化せよ。ただし、一人が両チームに所属することはできない。

やりかた

DP。
dp[i][w][b]:=（i人目まで見たときに白チームにw人、黒チームにb人選抜したときの最大値）で動的計画法。

以下ソース。

int dp[1010][16][16];
vector<pair<int, int> > p;
int rec(int idx, int w, int b){
  if(idx == p.size()){
    if(w == 15 && b == 15) return 0;
    else return -INF;
  }
  if(dp[idx][w][b] != -1) return dp[idx][w][b];
  
  int ret = -INF;
  ret = max(ret, rec(idx + 1, w, b));
  if(w < 15) ret = max(ret, rec(idx + 1, w + 1, b) + p[idx].first);
  if(b < 15) ret = max(ret, rec(idx + 1, w, b + 1) + p[idx].second);
  return dp[idx][w][b] = ret;
}

int main(int argc, char **argv){
  int a, b;
  while(cin >> a >> b)
    p.push_back(make_pair(a, b));
  FILL(dp, -1);
  cout << rec(0, 0, 0) << endl;
  return 0;
}