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];
	}

};