SRM527 Div1 Easy(275), Div2 Medium(550) P8XGraphBuilder

P8XGraphBuilder

動的計画法。点数がiで木の数がjの森の最大コスコアを覚えておけば良い。それぞれの木に片方だけが繋がった辺（？）が１本ずつあるとして計算しておくと楽。点数が２以上ならば次数１の頂点が少なくとも１個あるはずなので、そこを最後にする。

#include <string>
#include <vector>
using namespace std;

class P8XGraphBuilder{public:
int solve( vector <int> scores )
{
    int N = (int)scores.size()+1;

    //  S[i][j]
    //  点数i木の数jの森の、それぞれの木に辺を１つ加えた最大スコア
    vector<vector<int> > S( N, vector<int>(N) );
    S[1][1] = scores[0];

    for ( int i=2; i<=N-1; i++ )
    {
        for ( int j=1; j<=i-1; j++ )
            S[i][1] = max( S[i][1], S[i-1][j]+scores[j] );
        for ( int j=1; j<=i; j++ )
            for ( int k=1; k<=i-(j-1); k++ )
                S[i][j] = max( S[i][j], S[k][1]+S[i-k][j-1] );
    }

    return S[N-1][1]+scores[0];
}};