コード進行 [yukicoder 1111]

https://yukicoder.me/problems/no/1111

前提知識

• 動的計画法

解説

https://yukicoder.me/submissions/510572

mod10⁹+7数え上げなので、まずはDP。
先頭から順番に決めていくとして、最後の要素だけがそれ以降の処理に関係してくるし…DPだな

動的計画法

dp[i][k][lst] := i番目までコードが確定していて、現状の複雑度がkであり、最後のコードがlstである組合せ

ちょっと複雑なDPを練習している諸君は割とすぐ思いつくかもしれない。
先頭からi番目まで確定している状態で、抽象化に必要な特徴量としては「複雑度」と「最後のコード」なので、
これを状態に持たせる。

状態数は既に2710⁶なので、遷移であまり無茶はできない。
遷移としては、次にどのコードを持ってくるかという選択なので、300通りの選択肢が考えられる。
これを愚直にやってしまうと、9110⁸なので、無理っぽくないというレベル（というかTLEしました）。
そこで、遷移先を必要なものだけに限定する。

遷移先を必要なものだけに限定

最後のコードと次のコードを全探索すると、300×300通りとなるが、
最後のコードと次のコードのうち、使えるコード進行に限定すると、M通りに削減することができる。
これで計算量を削減しよう。
この削減テクは、グラフの探索をするときに隣接行列を使うよりも、隣接グラフを使う方が計算量がいいのと同じ原理。
なので、
E[lst] := {使えるコード進行の先, 複雑度}の配列
を使って、必要な遷移先だけにループを限定すると、通る。
O(NMK)

int N, M, K;
vector<pair<int, int>> E[303];
mint dp[303][606][303];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;

    rep(i, 1, 301) E[0].push_back({ i, 0 });
    rep(i, 0, M) {
        int a, b, c; cin >> a >> b >> c;
        E[a].push_back({ b, c });
    }

    dp[0][0][0] = 1;
    rep(i, 0, N) rep(k, 0, K + 1) rep(lst, 0, 301) {
         fore(p, E[lst]) dp[i + 1][k + p.second][p.first] += dp[i][k][lst];
    }

    mint ans = 0;
    rep(lst, 1, 301) ans += dp[N][K][lst];
    cout << ans << endl;
}