POJ 2626 - Chess

http://poj.org/problem?id=2626

概要

30人のチェスプレイヤーを選出したい． 30人のうち，15人は白でプレイし，残りの15人は黒でプレイする． 各プレイヤーには白での能力値と黒での能力値がそれぞれ設定されている． このとき，能力値の合計を最大化する問題．

制約

解法

dp[i][j][k] = i 人目までの選手で，白のプレイヤーを j 人，黒のプレイヤーを k 人選んだときの，能力値の合計の最大値

という DP．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   vector<pair<int,int> > v;
 8   int w, b;
 9   while (cin >> w >> b) {
10     v.push_back(make_pair(w, b));
11   }
12 
13   const int N = v.size();
14   vector<vector<vector<int> > > dp(N+1, vector<vector<int> >(16, vector<int>(16, 0)));
15   for (int i = 0; i < N; i++) {
16     for (int j = 0; j <= 15; j++) {
17       for (int k = 0; k <= 15; k++) {
18         // skip i
19         dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k]);
20         // choose i as white
21         if (j+1 <= 15) {
22           dp[i+1][j+1][k] = max(dp[i+1][j+1][k], dp[i][j][k] + v[i].first);
23         }
24         // choose i as black
25         if (k+1 <= 15) {
26           dp[i+1][j][k+1] = max(dp[i+1][j][k+1], dp[i][j][k] + v[i].second);
27         }
28       }
29     }
30   }
31   cout << dp[N][15][15] << endl;
32   return 0;
33 }
poj/2626.cc