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];
	}
};