ノード数が $N$ で辺の数が $N-1$ である連結なグラフを考えます。
与えられる要素が $N-1$ 個の配列 $\mathrm{score}$ において、次数が $d$ のノードには $\mathrm{score}[d-1]$ 点をつけます。
ノードごとの点数の合計値が最大になるようにグラフを作ったとき、その最大値を求めてください。
・$1 \le$ 配列の要素数 $\le 50$
・$0 \le$ 各要素の値 $\le 10{,}000$
絵を見ると無向グラフを考えなさい、ということのようである。
特に明記されてはいないが、このグラフは木である。
次数の総和は "辺の数 $\times 2$" になるので（辺はそれぞれ $2$ 個の端点を持つから、と考えると直感的かも）、
dp[i番目のノード][次数] := スコアの最大値
という DP が使えて、
dp[N][2*(N-1)] が答えになる。
#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;
}
(ΦωΦ)＜
つづく