TopCoder SRM 527 Div1 Easy P8XGraphBuilder

問題

n+1個の頂点とn個の辺からなる連結なグラフを自由に作る。
次数がdの頂点にはscore[d-1]の点数がつく。

グラフ全体の点数は各頂点の点数の和である。
グラフの点数の最大値を求めよ。

制約条件

n≦50

方針

全次数の和は2*nに等しい。
頂点i個目までで次数をj消費したときの最大スコアをdp[i][j]とするようなDPにより解ける。

頂点数iで合計次数が2*nのグラフが任意に作れるかという問題は自明ではないという議論がtwitter上であった。
帰納法により示せるっぽい。

ソースコード

int dp[51][102];

class P8XGraphBuilder {
	public:
	int solve(vector <int> scores) 
	{
		int n=scores.size();
		memset(dp,-1,sizeof(dp));
		dp[0][0]=0;
		rep(i,n+1)rep(j,2*n)if(dp[i][j]>=0)for(int k=1;k<=n&&j+k<=2*n;k++)
			dp[i+1][j+k]=max(dp[i+1][j+k],dp[i][j]+scores[k-1]);
		return dp[n+1][2*n];
	}