[ブルーブリッジカップ2018初戦]テスト回数

テーマはx星の住民の気性があまりよくないことを説明していますが、彼らが怒っている間に唯一の異常な行動は携帯電話を落とすことです.各メーカーも、耐投型携帯電話を次々と発売している.x星の品質監督局は、携帯電話が耐投試験を経なければならないことを規定し、耐投指数を評価してから、上場流通を許可した.x星には雲にそびえる高い塔がたくさんあり、ちょうど耐投テストに使えます.塔の各層の高さは同じで、地球とは少し違いますが、彼らの最初の層は地面ではなく、私たちの2階に相当します.携帯電話が7階から落ちても壊れなかったが、8階が壊れた場合、携帯電話の耐投指数=7になる.特に、携帯電話が1階から落ちて壊れてしまうと、耐投指数=0になります.タワーの最上階のn階に着いても壊れていなければ、耐投指数=nはテスト回数を減らすため、メーカーごとに3台の携帯電話をサンプリングしてテストに参加する.あるテストの塔の高さは1000階で、もし私たちがいつも最適な戦略を採用すれば、最悪の運の下で最大何回テストして携帯電話の耐投指数を確定する必要がありますか?
出力出力は整数で答えを表す
構想——動的計画動的計画方程式:f[i][j]iは携帯電話の個数を表し、jはフロア数を表す.i=1のとき、つまりj階建てのビルごとに、私たちはj回転ばなければなりません.これは実際には最善の戦略であり、私たちは徐々に上へ拡張することができます.i-1台の携帯電話をすべてのフロアに対する回数を見つけたと仮定し、i台の携帯電話がある場合のテスト回数を求めます.そのため、現在のフロアk(1~j-1)を巡る必要があります.k階で壊れたと仮定すると、i-1台の携帯電話をk-1階のビルの最悪の場合dp[i-1][k-1]+1を選択します.k階で壊れていなければ、i台の携帯電話を選択して、残りのj-k階の最悪の場合dp[i][j-k]+1を選択することができます.最悪の運なので、両者の間で最大値を取る必要がありますが、私たちは最適な戦略を取るので、最小値を取る必要があります.すなわち、d[i][j]=min(dp[i][j],max(dp[i-1][k-1],dp[i][j-k])+1);
ACコード

#include
using namespace std;

int f[5][1005];

int main(){
	for(int i=1;i<=3;i++){
		for(int j=1;j<=1000;j++){
			f[i][j]=j;
		}
	}
	
	for(int j=1;j<=1000;j++){
		for(int i=2;i<=3;i++){
			for(int k=2;k<j;k++){
				f[i][j]=min(f[i][j],max(f[i-1][k-1]+1,f[i][j-k]+1));
			}
		}
	}
	cout<<f[3][1000]<<endl;
	return 0;
}