PS와 개발을 공부하자

Topcoder SRM 527 Div1(Easy) P8XGraphBuilder 본문

Algorithm/Problem Solving

Topcoder SRM 527 Div1(Easy) P8XGraphBuilder

sgc109 2017.07.14 15:42
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로는 바로 연결되기때문에.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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 == 0return (!degree && !nodeCnt ? 0 : -inf);
        int& cache = dp[pos][degree][nodeCnt];
        if(cache != -1return 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, -1sizeof(dp));
        int ret = go(02 * n, n + 1);
        return ret;
    }
};
cs


0 Comments
댓글쓰기 폼