ダイナミックサンプル1

1920 ワード
テキストリンク

ポリシー


1)最初は演算回数を減らさなければならないので,条件をif/else ifに割り込む.
思いついた.すなわち、a.5に分けることができれば5に分け、ゲートサイクルに対して増加し、
残りの操作b,c,d条件文を完了する.

  • しかし、このように書くと、例を挙げて説明する26は成り立たない.
    前述したように、1を減算することは、計算の優先度が最も低い.
    26->13->12->4->2->1:合計5回の演算が最小!そう思います.

  • たとえば、26->25->5->1です.
    上の1)は誤った考えを証明することができる.

    • そっと



    ->if~else if~で区別するのではなく、個別に条件を定めます.
    そこから最小演算量を見つける必要があると判断することもできる.

    点火式を作ろう。


    :nを1に生成できる最小演算数はいくらですか?
    dp[n] = dp[n/5] + 1;
    ->ここで+1は演算を1回行ったことを示す.
    dp[n] = dp[n/5] + 1;
    dp[n] = dp[n/3] + 1;
    dp[n] = dp[n/2] + 1;
    dp[n] = dp[n - 1] + 1;
    このように表現することができます.次に例外処理を追加します.
    最小演算であるため、各dp[n]演算と同時に最小値を更新すればよい.

    ソースコード

    #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main() {

	int n;
	cin >> n;

	vector<int>dp(n + 1, 0);

	dp[1] = 0;
	
	for (int i = 2; i <= n; i++)
	{
		dp[i] = dp[i - 1] + 1;

		if (i % 5 == 0)
		{
			dp[i] = min(dp[i / 5] + 1,dp[i]);
		}
		
		if (i % 3 == 0)
		{
			dp[i] = min(dp[i / 3] + 1, dp[i]);
		}

		if (i % 2 == 0)
		{
			dp[i] = min(dp[i / 3] + 1, dp[i]);
		}
	}
	cout << dp[n];
	return 0;
}
    AAC高品質符号化(ffmpeg)
    [Java Script]「整数平方根判別」