[BOJ]1463:1

5719 ワード
白駿 DP boj C ダイナミックプログラミング アルゴリズム#アルゴリズム# テキストリンク

💉質問内容


問題に答える

💉にゅうしゅつりょく


🧺入力
第1行は、1以上10以下の6乗の整数Nを与える.
🧺しゅつりょく
1行目の演算回数の最大値を出力します.

🔋サンプルI/O


🔮入力例1
2
🔮サンプル出力1
1
🔮入力例2
10
🔮サンプル出力2
3

💉もんだいぶんせき


🔋ぶんかつ


ダイナミックプログラミング(DP)

🔋難易度


シルバーIII

💉問題を解く


🔋解法


まず2からNまで繰り返し文を回した
最初のインデックスの値はゼロでなければならないからです.
また、次の条件を満たす必要があります.
まず、iインデックスの値はi-1インデックスの値1より大きくなければならない.
  • 2で区切られた数字は、すぐに小さなi値と値を使用して比較されます.
  • 3で区切られた数字は、すぐに小さなi値と値を使用して比較されます.

    • 🔋ソースコード

    #include <bits/stdc++.h>

constexpr int MAX = 10e6 + 1;

int adj[MAX];

void dp(int N) {
	for (int i = 2; i <= N; ++i) {
		adj[i] = adj[i - 1] + 1;
		if (i % 3 == 0) adj[i] = std::min(adj[i], adj[i / 3] + 1);
		if (i % 2 == 0) adj[i] = std::min(adj[i], adj[i / 2] + 1);
	}
}

int main() {
	int N;
	std::cin >> N;

	dp(N);
	std::cout << adj[N];
}
    最初はGRADYで解こうとしたが、時間は0.15秒だった.
    だから途中で作った時にDPに変えました
    小条件四半期のため、2回間違えた.ううう
    dpはもう少し練習する必要があります.銀色に戸惑う...
    大会の問題は簡単でなければ少なくとも銀色I~金以上はあるだろう.

    💉終了時..。


    気になるところがあればコメントで質問しましょう~~
    AT LINE SELECTIONの使い方
    2018-09-29漁船データの信号伝送成功率レポート(全統計)