SRM465 Div2 Hard(1000) WeirdTimes

WeirdTimes

i番目の時間をhとしたときにi+1番目以降の時間の選び方の数をC_i,hとする。
C_i,h = Σ_j=h²³C_i+1,j（分が進んでいる場合）,　= Σ_j=h+1²³C_i+1,j（進んでいない場合）
の動的計画法でC_i,hが求まる。
最初の時間はΣ_i=0^hC_0,i≦K＜Σ_i=0^h+1C_0,iが成り立つようなh。２番目以降も同様。
桁あふれ注意。

#include <vector>

using namespace std;

class WeirdTimes
{
public:
    vector <int> hourValues( vector <int> minuteValues, int K );
};

vector <int> WeirdTimes::hourValues( vector <int> minuteValues, int K )
{
    int n = (int)minuteValues.size();

    //  [i][h] i番目の時間がhだったときの
    //  i+1番目以降の時間の選び方の数
    vector<vector<int> > C( n, vector<int>( 24, 0 ) );

    for ( int h=0; h<24; h++ )
        C[n-1][h] = 1;

    for ( int i=n-2; i>=0; i-- )
    for ( int h=0; h<24; h++ )
    {
        int t = minuteValues[i+1] > minuteValues[i] ? h : h+1;
        for ( int j=t; j<24; j++ )
            C[i][h] = min( C[i][h] + C[i+1][j], 1000000000 );
    }

    //  先頭から時間を決めていく
    K--;
    vector<int> hour( n );
    int h = 0;
    for ( int i=0; i<n; i++ )
    {
        if ( i > 0  &&  minuteValues[i-1] >= minuteValues[i] )
            h++;

        for ( ; h<24; h++ )
        {
            if ( K < C[i][h] )
                break;

            K -= C[i][h];
        }

        if ( h >= 24 )
            return vector<int>( 1, -1 );

        hour[i] = h;
    }

    return hour;
}