[Codeforces] Round #549 B. Nirvana

Nirvana

https://codeforces.com/contest/1143/problem/B

方針

桁毎に考えていきます。なので、桁DPを適用します。

\( dp[i][0]\) を \(n\) の \( i \) 桁目までの積とし、\(dp[i][1]\) を \(n \) 以下の整数の \( i\) 桁目までの積の最大値とします。

ここで、初期値は、\( i \) 桁を \( d_i \) として、

  • \(d_n = 1\) のとき

\(dp[1][0] = 1, \ dp[1][1] = 1\)

  • \(d_n \neq 1\) のとき

\(dp[1][0] = d_n, \ dp[1][1] = d_n – 1\)

のように設定します。

\(dp[i][1]\) の更新は、

\[dp[i + 1][1] = \max (dp[i][0] * (d_{i + 1} – 1),\ dp[i][1] * 9 )\]

とします。

コード

シェアする

  • このエントリーをはてなブックマークに追加

フォローする