SRM462 Div2 Hard(1000) SteeplechaseTrack

TopCoder

SteeplechaseTrack

動的計画法。i個目のフェンスとしてフェンスjを跳んだ後の複雑さの最大値をci,jとする。

ci,j = max{ ci-1,k | ci-1,kが有効で、k→jに道がある }

である。

全ての有効なci,jに終点までの複雑さを足したものの最大値を求める。

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class SteeplechaseTrack
{
public:
    int maxComplexity( vector <string> fences, vector <string> tracks, int N );
};

int SteeplechaseTrack::maxComplexity( vector <string> fences, vector <string> tracks, int N )
{
    int n = (int)fences.size();

    //  [i][j]　i+1個目のフェンスとしてフェンスjを跳んだ後の複雑さの最大値
    vector<vector<int> > comp( N, vector<int>( n ) );

    for ( int j=0; j<n; j++ )
        if ( fences[j][1] != '0' )
            comp[0][j] = fences[j][0]-'0' + fences[j][1]-'0';

    for ( int i=1; i<N; i++ )
        for ( int j=0; j<n; j++ )
        for ( int k=0; k<n; k++ )
            if ( comp[i-1][k] != 0  &&  tracks[k][j] != '0' )
                comp[i][j] = max( comp[i][j],
                    comp[i-1][k] + tracks[k][j]-'0' + fences[j][0]-'0' );

    //  最大値
    int m = -1;

    for ( int i=0; i<N; i++ )
        for ( int j=0; j<n; j++ )
            if ( comp[i][j] != 0  &&  fences[j][2] != '0' )
                m = max( m, comp[i][j] + fences[j][2]-'0' );

    return m;
}