MemberSRM468 Div1 500 RoadOrFlightHard

本番で解けなかった問題．
DP中で，飛行機を使う最適な区間は…とか考えてて意味不明な事になってたものの，

• 飛行機でK回目のフライト中
• K回のフライトを終えて陸地を移動中

という状態だけ保存してDPすれば良かった．

この手の問題はまだまだ訓練が必要そう…．

#include <iostream>
#include <vector>

using namespace std;

class RoadOrFlightHard{
private:
    void generate(int N, vector<long long> &res, int first, int prod, int add, int mod){
        res.resize(N);
        res[0] = first%mod;
        for(int i=1;i<N;i++)
            res[i] = (res[i-1]*prod+add)%mod;
    }
public:
    long long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod, int flightFirst, int flightProd, int flightAdd, int flightMod, int K){
        vector<long long> road, flight;
        generate(N, road, roadFirst, roadProd, roadAdd, roadMod);
        generate(N, flight, flightFirst, flightProd, flightAdd, flightMod);
        long long curR[41], curF[41], nextR[41], nextF[41];
        memset(curR, 0, sizeof(curR));
        memset(curF, 0, sizeof(curF));
        for(int i=0;i<N;i++){
            nextR[0] = curR[0]+road[i];
            nextF[0] = (long long)1e15;
            for(int j=1;j<=K;j++){
                nextR[j] = min(curR[j], curF[j])+road[i];
                nextF[j] = min(curR[j-1], curF[j])+flight[i];
            }
            memcpy(curR, nextR, sizeof(curR));
            memcpy(curF, nextF, sizeof(curF));
        }
        return min(curR[K], curF[K]);
    }
};