SRM468 Div1 Medium

500
DP[街][フライトの回数][最後に利用した交通手段]
移動のパターンは、road -> road, flight -> flight, road -> flight, flight -> road の 4 つ
[街]をNまで確保すると死ぬ。手元だと確保できるから気付かずにサブミットしてしまった。
直前のだけ覚えておけば答えは出せる。

const int N_ = 400000 + 5;
const int K_ = 40 + 5;
lli rTime[N_];
lli fTime[N_];
lli g[2][K_][2];

class RoadOrFlightHard {
public:
  long long minTime(int N,
                    int rFirst, int rProd, int rAdd, int rMod,
                    int fFirst, int fProd, int fAdd, int fMod,
                    int K)
  {
    rTime[0] = rFirst % rMod;
    for (int i = 1; i < N; ++i) {
      rTime[i] = (rTime[i - 1] * rProd + rAdd) % rMod;
    }

    fTime[0] = fFirst % fMod;
    for (int i = 1; i < N; ++i) {
      fTime[i] = (fTime[i - 1] * fProd + fAdd) % fMod;
    }

    const int R = 0, F = 1;
    const lli inf = 1LL << 60;
    fill(&g[0][0][0], &g[2 - 1][K_ - 1][2], inf);
    g[0][0][R] = 0;

    for (int n = 0; n + 1 < N + 1; ++n) {      
      int m = (n + 1) % 2;
      for (int i = 0; i < K_; ++i) {
        g[m][i][R] = g[m][i][F] = inf;
      }
      for (int k = 0; k < K + 1; ++k) {
        g[m][k][R] = min(g[m][k][R], g[n % 2][k][R] + rTime[n]);
        g[m][k][F] = min(g[m][k][F], g[n % 2][k][F] + fTime[n]);
        g[m][k][R] = min(g[m][k][R], g[n % 2][k][F] + rTime[n]);
        if (k + 1 < K + 1) {
          g[m][k + 1][F] = min(g[m][k + 1][F], g[n % 2][k][R] + fTime[n]);
        }
      }
    }

    lli mn = inf;
    for (int i = 0; i < K + 1; ++i) {
      mn = min(mn, g[N % 2][i][F]);
      mn = min(mn, g[N % 2][i][R]);
    }
    return mn;
  }

};