問題
http://community.topcoder.com/stat?c=problem_statement&pm=11308&rd=14552
解き方
ｄｐで解く。最終的に２＊ｎ−２個のエッジが発生する。
コード
class P8XGraphBuilder {
public: int solve(vector<int> scores) {
int n=scores.size()+1;
int dp[n+1][2*n-1];
FORE(i,0,n+1)FORE(j,0,2*n-1)dp[i][j]=-(1e+9);
dp[0][0]=0;
for(int i=0;i<n;i++)for(int j=i;j<2*n-2;j++){
for(int k=0;k<n-1&&j+k+1<=2*n-2;k++){
dp[i+1][j+k+1]=max(dp[i+1][j+k+1],dp[i][j]+scores[k]);
}
}
return dp[n][2*n-2];
}
};
public: int solve(vector<int> scores) {
int n=scores.size()+1;
int dp[n+1][2*n-1];
FORE(i,0,n+1)FORE(j,0,2*n-1)dp[i][j]=-(1e+9);
dp[0][0]=0;
for(int i=0;i<n;i++)for(int j=i;j<2*n-2;j++){
for(int k=0;k<n-1&&j+k+1<=2*n-2;k++){
dp[i+1][j+k+1]=max(dp[i+1][j+k+1],dp[i][j]+scores[k]);
}
}
return dp[n][2*n-2];
}
};