SRM 527 275pt : P8XGraphBuilder
問題概要
次数に対するスコアが与えられる。ノード数N(<50)の木で、各ノードは次数に応じたスコアを得る。獲得できるスコアを最大化する問題。
解法
1~Nの組み合わせで次数の合計が2*(N-2)になるように選ぶ。そのような次数列を持つ木が作れることは帰納的に示せる。
acceptされたコード
計算量O(N^3)。
#include <vector> #include <algorithm> using namespace std; const int MAX_N = 51; const int INF = 1<<29; int dp[MAX_N+1][2 * MAX_N - 1]; struct P8XGraphBuilder { int solve(vector <int> scores) { const int N = scores.size() + 1; for(int i=0; i<=N; i++){ fill(dp[i], dp[i] + (2*N - 1), -INF); } dp[0][0] = 0; for(int k=0; k<N; k++){ for(int i=1; i<N; i++){ for(int j=0; i+j<2*N-1; j++)if(dp[k][j] != -INF){ dp[k+1][j+i] = max(dp[k+1][j+i], dp[k][j] + scores[i-1]); } } } return dp[N][2*N-2]; } };