cafelier@SRM

SRM527 275

あとで | 05:24 |

みんなDPだった。Easyだからもっと格好いい解があるのかとずっと考えてしまいました…。

• 「Nノード ＆ N-1エッジ ＆ 連結 ＝ 木」という知識だけ使う

class P8XGraphBuilder { public:
   int solve(vector <int> scores)
   {
      scores.insert(scores.begin(), 9999999); // 1ずれてると扱いにくいので
      const int N = scores.size();

      // 葉の個数を全パターン試して良いのを取る
      int best = 0;
      for(int leaves=1; leaves<N; ++leaves)
         best = max(best, scores[1]*leaves + calc(leaves, N-leaves, scores));
      return best;
   }

   // 葉がleaves個、葉以外がnodes個の木のベストスコア
   map<pair<int,int>,int> memo;
   int calc(int leaves, int nodes, const vector<int>& scores)
   {
      // nodes==1 なら根を作らないといけないので全部
      if( nodes == 1 )
         return scores[leaves];

      // メモ化
      pair<int,int> key(leaves, nodes);
      if( memo.count(key) )
         return memo[key];

      // 適当にk個選んで1つのノードを親にする
      // この親ノードは根では無いので次数は k+1。
      int best = 0;
      for(int k=1; k<=leaves; ++k)
         best = max(best, scores[k+1] + calc(leaves-k+1, nodes-1, scores));
      return memo[key] = best;
   }
};