SRM 527 Div2 Medium P8XGraphBuilder

問題

サイズNの連結グラフを考える.
各次数のスコアが与えられたとき,全体の最大スコアを求める

解答

次数i以下で構成されたグラフの最大スコアを考える.
サイズNで次数iのノードを含むとき,i+1のグラフ(次数iのノードが1個,次数1のノードがi-1個)とN-i+1のグラフを考える.
この時の最大スコアはi+1の(次数iを含む)グラフのスコア+N-i+1の最大スコア-次数1のスコア(前者の次数1のノードは後者で数え上げられているため)
次数の小さい方から考え動的計画法で求めていけば,サイズNの最大スコアを求めることが出来る.

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