SRM468 Div1 Medium(500) RoadOrFlightHard

RoadOrFlightHard

動的計画法。何回離陸したかと直前が陸路か空路か、それぞれの最小所要時間を記憶しておく。

#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

class RoadOrFlightHard
{
public:
    long long minTime( int N, int roadFirst, int roadProd, int roadAdd, int roadMod, int flightFirst, int flightProd, int flightAdd, int flightMod, int K );
};

long long RoadOrFlightHard::minTime( int N, int roadFirst, int roadProd, int roadAdd, int roadMod, int flightFirst, int flightProd, int flightAdd, int flightMod, int K )
{
    //  T[k][0]：k回離陸して直前に陸路を選択した場合の最小所要時間
    //  T[k][1]：k回離陸して直前に空路を選択した場合の最小所要時間
    vector<long long> T[2];
    T[0] = T[1] = vector<long long>( K+1, LLONG_MAX/2 );
    T[0][0] = 0;
    
    long long proad;    //  直前の陸路の所要時間
    long long pflight;  //  直前の空路の所要時間

    for ( int n=0; n<N; n++ )
    {
        long long road, flight;

        if ( n == 0 )
            road   = roadFirst   % roadMod,
            flight = flightFirst % flightMod;
        else
            road   = ( proad   * roadProd   + roadAdd   ) % roadMod,
            flight = ( pflight * flightProd + flightAdd ) % flightMod;

        vector<long long> t[2] = { T[0], T[1] };

        //  陸路
        for ( int k=0; k<=K; k++ )
            T[0][k] = min( t[0][k], t[1][k] ) + road;

        //  空路
        for ( int k=1; k<=K; k++ )
            T[1][k] = min( t[0][k-1], t[1][k] ) + flight;

        proad   = road;
        pflight = flight;
    }

    return min( *min_element( T[0].begin(), T[0].end() ),
                *min_element( T[1].begin(), T[1].end() ) );
}