SRM 527 div1 easy: P8XGraphBuilder

SRM 527 の練習会に参加しました。
easy med 解いてドヤ顔したと思ったら easy 間違えててダメでした。

問題

TopCoder Statistics - Problem Statement

解法

頂点数 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];
    }
};