dp初步：以时间序为基准的动态规划

时间不会倒流，时间轴上靠后发生的不会影响前面的事，具有无后效性，因此很多时候结合时间来设状态，并用刷表法进行转移，是一种很好的做法。

例题

CF1840F Railguns

题解博客

这题将某人在第 $k$ 秒能否 停留在点 $(i,j)$ 上设为状态 dp[i][j][k] 进行转移，一个人在某个时间要么停留，要么往右/往下走，于是可以列出更新公式（转移方程）。

P2583 地铁间谍

P2583

这题将某人在第 $i$ 秒停留在站台 $j$ 所需的最小停留时间设为状态 dp[i][j] 进行转移，一个人在某个时间要么停留等待，要么坐车往右/往左走一站，于是可以列出更新公式（转移方程）。

int solve() {
    mem(has_train, 0);
    mem(dp, -1);
    cin >> T;
    rep(i, 1, n - 1) { cin >> t[i]; }
    cin >> m;
    rep(j, 1, m) {
        int x;
        cin >> x;
        int tt = x;
        rep(i, 1, n) {
            if (tt <= T)
                has_train[tt][i][0] = 1;
            tt += t[i];
        }
    }
    cin >> m;
    rep(j, 1, m) {
        int x;
        cin >> x;
        int tt = x;
        per(i, n, 1) {
            if (tt <= T)
                has_train[tt][i][1] = 1;
            tt += t[i - 1];
        }
    }
    dp[0][1] = 0;
    rep(i, 0, T) {
        rep(j, 1, n) {
            if (dp[i][j] == -1)
                continue;
            //            cout << i << "," << j << ": \n";
            upd(dp[i + 1][j], dp[i][j] + 1);
            if (has_train[i][j][0] && j != n && i + t[j] <= T)
                upd(dp[i + t[j]][j + 1], dp[i][j]);
            if (has_train[i][j][1] && j != 1 && i + t[j - 1] <= T)
                upd(dp[i + t[j - 1]][j - 1], dp[i][j]);
            //    cout << dp[i][j] << " ";
        }
        //    cout << endl;
    }
    return dp[T][n];
}