SRM 527 div1 easy: P8XGraphBuilder
SRM 527 の練習会に参加しました。
easy med 解いてドヤ顔したと思ったら easy 間違えててダメでした。
解法
頂点数 n の木は, すべての頂点が次数 1 以上 n-1 以下, 次数の合計が 2n-2 という条件を満たせば何でも OK です。
この場合, まず次数が 2 以上の頂点をまず一直線につなげて, その後次数 1 の頂点を次数が合うようにくっつければ良いからです。
ということで, dp[n][sum] = (n 頂点目の時点で次数の和が sum であるような場合の, スコア合計の最大値) という dp を用いて, dp を解けば良いです。
const int INF = 1e8; int dp[55][110]; class P8XGraphBuilder { public: int solve(vector <int> scores) { int n = scores.size()+1; for (int i = 0; i <= n; i++) for (int j = 0; j <= 2*n-2; j++) { dp[i][j] = -INF; } dp[0][0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < 2*n-2; j++) { if (dp[i][j] < 0) continue; for (int k = 1; k < n; k++) { if (j+k > 2*n-2) continue; dp[i+1][j+k] = max(dp[i+1][j+k], dp[i][j]+scores[k-1]); } } } return dp[n][2*n-2]; } };