SRM527 Div1 Easy - P8XGraphBuilder
問題
n頂点の木を自由に作る
次数がiの頂点1つにつきスコアにa[i]が加算される(1 <= i <= n-1)
スコアの最大値を求めよ
2 <= n <= 51
0 <= a[i] <= 10^4
解法
木だから次数1の頂点が2個は絶対に出来る
残りn-2個の頂点の次数は、各次数が1以上n-1以下 かつ 次数の総和が2n-4であれば任意の組み合わせが実現できる(帰納法で示せる)
dp[i][j]: i個目の頂点までで次数をj個使った場合のスコアの最大値
とすればO(n^3)で解ける
class P8XGraphBuilder { public: int solve(vector<int> a) { int n = a.size()+1, s = 2*n-4, dp[55][111] = {}; memset(dp, -1, sizeof(dp)); dp[0][0] = 2*a[0]; rep(i,n-2) rep(j,111) reps(k,1,n) if (dp[i][j]!=-1 && j+k<=s) chmax(dp[i+1][j+k], dp[i][j]+a[k-1]); return dp[n-2][s]; } };