第9回ブルーブリッジカップ省試合C++B組第4題

5773 ワード

テスト回数


x星の住民は性格が悪いが、彼らが怒っている間に唯一の異常な行動は携帯電話を落とすことだ.各メーカーも、耐投型携帯電話を次々と発売している.x星の品質監督局は、携帯電話が耐投試験を経なければならないことを規定し、耐投指数を評価してから、上場流通を許可した.x星には雲にそびえる高い塔がたくさんあり、ちょうど耐投テストに使えます.塔の各層の高さは同じで、地球とは少し違いますが、彼らの最初の層は地面ではなく、私たちの2階に相当します.携帯電話が7階から落ちても壊れなかったが、8階が壊れた場合、携帯電話の耐投指数=7になる.特に、携帯電話が1階から落ちて壊れてしまうと、耐投指数=0になります.タワーの最上階のn階に着いても壊れていなければ、耐投指数=nはテスト回数を減らすため、メーカーごとに3台の携帯電話をサンプリングしてテストに参加する.あるテストの塔の高さは1000階で、もし私たちがいつも最適な戦略を採用すれば、最悪の運の下で最大何回テストして携帯電話の耐投指数を確定する必要がありますか?この最大テスト回数を記入してください.
注意:記入する必要があるのは整数で、余分な内容を記入しないでください.
この問題は長い間考えてやっと分かったので、今日はわざわざ整理して、ダイナミックな計画の思想を使って、ネット上の答えを参考にしましたが、多くはコードだけで、はっきり言えません.分からないことがあれば、下で評論して、交流してください.
#include <iostream>
#include <cmath>

using namespace std;

int dp[50][1005];
int main()
{
    int phone,floor;
    cin >> floor >> phone;
    for(int i=1;i<=phone;i++)
	{
		for(int j=1;j<=floor;j++)
			dp[i][j]=j;  /// i j j , 
	}
	for(int i=2;i<=phone;i++)
	{
		for(int j=1;j<=floor;j++)
		{
			for(int k=1;k<j;k++)  /// k 
				dp[i][j]=min(dp[i][j],max(dp[i-1][k-1],dp[i][j-k])+1);
		}
	}
    cout << dp[phone][floor];
    return 0;
}