Top
TopCoder SRM 527 Div1 Easy / Div2 Med "P8XGraphBuilder"
ノード数が NN で辺の数が N−1N-1 である連結なグラフを考えます。
与えられる要素が N−1N-1 個の配列 score\mathrm{score} において、次数が dd のノードには score[d−1]\mathrm{score}[d-1] 点をつけます。
ノードごとの点数の合計値が最大になるようにグラフを作ったとき、その最大値を求めてください。
・1≤1 \le 配列の要素数 ≤50\le 50
・0≤0 \le 各要素の値 ≤10,000\le 10{,}000

絵を見ると無向グラフを考えなさい、ということのようである。
特に明記されてはいないが、このグラフは木である。

次数の総和は "辺の数 ×2\times 2" になるので（辺はそれぞれ 22 個の端点を持つから、と考えると直感的かも）、
dp[i番目のノード][次数] := スコアの最大値
という DP が使えて、dp[N][2*(N-1)] が答えになる。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
using namespace std;

class P8XGraphBuilder { public: int solve(vector<int> scores); };

int P8XGraphBuilder::
solve(vector<int> scores) {
  int n = scores.size(),
      N = n + 1;
  vector<vector<int>> dp(N+1, vector<int>(2*N, -1)); // dp[N+1][2*N]
  dp[0][0] = 0;
  for(int i=0; i<N; ++i) {
    for(int prev=0; prev<2*N; ++prev) { // 今までの次数
      if(dp[i][prev] == -1) { continue; }
      for(int cur=1; prev+cur<=2*N-2; ++cur) { // 増やす次数
        dp[i+1][prev+cur] = max(dp[i+1][prev+cur], dp[i][prev] + scores[cur-1]);
      }
    }
  }
  int res = dp[N][2*N-2];
  return res;
}

(ΦωΦ)＜つづく