SRM527 Div1 Easy

275

dp[グラフの頂点数][葉の数]
解いたの忘れて2度目の挑戦。

class P8XGraphBuilder {
public:
  int solve(vector <int> scores)
  {
    const int N = 50 + 10;
    int dp[N][N];
    fill(&dp[0][0], &dp[N-1][N-1] + 1, -(1 << 29));
    dp[1][1] = 0;
    for (int sum = 0; sum < N; ++sum) {
      for (int leaf = 0; leaf < N; ++leaf) {
        if (dp[sum][leaf] < 0) continue;
        for (int add = 1; add <= scores.size(); ++add) {
          if (sum + add < N) {
            int m = (sum == 1 && leaf == 1) ? scores[add - 1] : scores[add];
            int& n = dp[sum + add][leaf - 1 + add];
            n = max(n, dp[sum][leaf] + m);
          }
        }
      }
    }
    int mx = 0;
    for (int i = 1; i < N; ++i) {
      mx = max(mx, dp[scores.size() + 1][i] + scores[0] * i);
    }
    return mx;
  }
};