[BOJ]キーボード(no.158)

質問する

キーボードはkriiが作った不思議なキーボードです.キーボードには4つのボタンしかありません.
画面にAを出力します.
CTRL-A:フルスクリーン選択
CTRL-C:選択したすべてのコンテンツをバッファにコピー
CTRL-V:バッファが空でない場合は、バッファの内容を画面出力文字列の真後ろに貼り付けます.
キーボードのボタンをN回押して、画面に出力されるAの数を最大にするプログラムを作成してください.
入力
第1行はN(1≦N≦100)を与える.
しゅつりょく
キーボードのボタンをN回押して、画面に出力できるA個の数の最値を出力します.

🤔 の意見を打診

ああ本当に辛いですね...

いつものように、最後の数を考慮して、ケースを共有しましょう.

注釈

dp[i]:i回で出力可能な最大A数

ヶーシング

1を押します.

dp[i] = dp[i-1] + 1

2を押します.

の最大値に達することはできません.無視

3を押します

2号と同じ

4を押します.

dp[i] = 2*dp[i-3]

まだ終わってない!
4番は前でずっと押すことができます(コピーは1回に何度でも貼り付けることができます)
i-4の値をコピーするとします.すると、合計2回iが貼り付けられるので、i-4の出力値は3倍になります.dp[i] = 3*dp[i-4]以下と正式化できる.二重for文でjという変数があると仮定する.dp[i] = j*dp[i-(j+1)]これまでの価格の中で、最も高いのは点火式だったはずだ.

🔥 てんかしき dp[i] = max(dp[i-1]+1, j*dp[n-(j+1)])

📌 説明する

import sys
input = sys.stdin.readline

N = int(input())
dp = [0]*101
dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3

for i in range(4,N+1):
    for j in range(2,i-2):
        dp[i] = max(dp[i-1]+1, j*dp[i-(j+1)], dp[i])

print(dp[N])

j範囲を探して少し頭が痛い

直接貼り付けが4の場合、最小値は既存出力値の数倍(2倍)

である.

の最大のケースは何倍か考えられます.(i-3倍)

レビュー

難しいですね。他のDPよりも、分機キャビネットの方が複雑です。 答えが出る前に、どれだけの症例があるかを考える習慣を身につけたと思います。 やっぱり練習が答えです。よく考えてから手配しましょう。