SRM 662 div1 med: ExactTree

気づかなかった…

問題

TopCoder Statistics - Problem Statement

解法

S(T)は,別の見方をすると,「ある頂点から別の頂点に向かうときに,それぞれの辺を何回通るか,の総和」とみなすことが出来ます(頂点単位でゴニョゴニョ考えるのではなく辺単位で考える)

ある辺を追加することを考えます。それが頂点数pの木と頂点数qの木(頂点数qの木はこれから頂点を伸ばしていって合計頂点数をnにする)につながる場合,その辺を通る経路の数は,頂点数pの木からq側の木に向かう経路の数分だけあるのでp*(n-p)です。

よって,dp[頂点数][余り] = 最小コスト というdpを作れば問題が解けます。

const int MAXN = 55;
const int MAXM = 101;
const int INF = 1e9;
int dp[MAXN][MAXM];

class ExactTree {
public:
    int getTree(int n, int m, int r) {
        for (int i = 0; i < MAXN; i++) for (int j = 0; j < MAXM; j++) dp[i][j] = INF;
        dp[1][0] = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                for (int x = 0; x < m; x++) for (int y = 0; y < m; y++) {
                    if (dp[j][x] >= INF || dp[i-j][y] >= INF) continue;
                    int z = dp[j][x] + dp[i-j][y] + j*(n-j);
                    dp[i][z%m] = min(dp[i][z%m], z);
                }
            }
        }
        int ans = dp[n][r];
        if (ans >= INF) ans = -1;
        return ans;
    }
};