おーじのゆるゆる精進日記 #4

みなさんはこれくらいのDPの実装は一瞬で済ませるんだろうなあ(泣)

トマトソース,クリームソース,バジルソース,のパスタがある(美味しそう).

3日連続して同じパスタを選んではならない.

K日分のパスタの予定(何ソースにするか)があらかじめ定まっている.

条件を満たす予定は何通り?

dp[i][j][k] := i日目にパスタj,i - 1日目にパスタkを食べる通り数

まずはDPの初期化ですが、これがなかなか厄介です.

4つに分けて説明します.

①一日目と二日目のパスタの予定があらかじめ定まっているとき

dp[2][(二日目の予定)][(一日目の予定)] = 1

②一日目のみパスタの予定があらかじめ定まっているとき

dp[2][1][(一日目の予定)] = 1

dp[2][2][(一日目の予定)] = 1

dp[2][3][(一日目の予定)] = 1

③二日目のみパスタの予定があらかじめ定まっているとき

dp[2][(二日目の予定)][1] = 1

dp[2][(二日目の予定)][2] = 1

dp[2][(二日目の予定)][3] = 1

④一日目も二日目もパスタの予定が定まっていないとき

全通り1(これは自明なので)

あとは遷移です.

遷移は以下の2通りです.

①i日目予定があらかじめ定まっているとき

dp[i][(i日目の予定)][j] += dp[i - 1][j][k]

(なおj,kは1以上3以下の整数で一日目の予定とjとkが等しい時はこの処理はしない)

②①じゃないとき

dp[i][j][k] += dp[i - 1][k][l]

(なおj,k,lは1以上3以下の整数でjとkとlが等しい時はこの処理はしない)

なぜj=k=lの時に処理を行わないかというと、3日連続して同じパスタを選ぶことは禁じられているからです.

とりあえず必要な情報は遷移に取り入れてみる.