Topcoder SRM 527 Div1(Easy) P8XGraphBuilder

https://community.topcoder.com/stat?c=problem_statement&pm=11308

풀이를 떠올린 속도는 나쁘지는 않았는데 cache 의 초기값을 -inf 로 안주고 0으로 줬다가 디버깅하느라 시간이 좀 걸렸다.
트리의 간선의 수 N이 정해지면 모든 노드들의 degree 의 합도 2N 으로정해지기 때문에 노드 수와 degree의 합이 N+1과 2N이 되게 하는 모든 degree의 조합의 최대 점수를 dp로 계산하면 된다.

트리의 노드 수와 트리 노드들의 degree 의 합만 기준에 일치한다면 각 노드의 degree 에 대한 조합이

어떻게 되던 그에 해당하는 트리를 만들 수가 있다는 사실을 캐치하는 것이 중요한 것같다.

이 것만 캐치하면 dp로는 바로 연결되기때문에.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
class P8XGraphBuilder {
public:
    vector<int> scores;
    int n;
    int dp[53][103][53];
    int go(int pos, int degree, int nodeCnt){
        if(pos == n || degree == 0 || nodeCnt == 0) return (!degree && !nodeCnt ? 0 : -inf);
        int& cache = dp[pos][degree][nodeCnt];
        if(cache != -1) return cache;
        cache = -inf;
        for(int i = 0 ; i * (pos + 1) <= degree && i <= nodeCnt; i++){
            cache = max(cache, scores[pos] * i + go(pos + 1, degree - i * (pos + 1), nodeCnt - i));
        }
        return cache;
    }
    int solve(vector<int> scores) {
        this->scores = scores;
        n = (int)scores.size();
        memset(dp, -1, sizeof(dp));
        int ret = go(0, 2 * n, n + 1);
        return ret;
    }
};