ブルーブリッジカップ-テスト回数
10740 ワード
タイトル:テスト回数
x星の住民は性格が悪いが、彼らが怒っている間に唯一の異常な行動は携帯電話を落とすことだ.
各メーカーも、耐投型携帯電話を次々と発売している.x星の品質監督局は、携帯電話が耐投試験を経なければならないことを規定し、耐投指数を評価してから、上場流通を許可した.
x星には雲にそびえる高い塔がたくさんあり、ちょうど耐投テストに使えます.塔の各層の高さは同じで、地球とは少し違いますが、彼らの最初の層は地面ではなく、私たちの2階に相当します.
携帯電話が7階から落ちても壊れなかったが、8階が壊れた場合、携帯電話の耐投指数=7になる.
特に、携帯電話が1階から落ちて壊れてしまうと、耐投指数=0になります.
タワーの最上階のn階に着いて投げて壊れなかったら、耐投げ指数=n
テスト回数を減らすため、メーカーごとに3台の携帯電話をサンプリングしてテストに参加する.
あるテストの塔の高さは1000階で、もし私たちがいつも最適な戦略を採用すれば、最悪の運の下で最大何回テストして携帯電話の耐投指数を確定する必要がありますか?
この最大テスト回数を記入してください.
注意:記入する必要があるのは整数で、余分な内容を記入しないでください.
答え:19
構想1:ダイナミックプランニング.
まず、もう一度問題を見てみましょう.メーカーごとに3台の携帯電話をサンプリングしてテストに参加します.あるテストの塔は1000階建てです.もし私たちがいつも最善の戦略を採用していたら、最悪の運の下で最大何回テストしなければ携帯電話の耐投指数を確定できませんか.ベスト・ポリシーとは何ですか.最悪の運の下とは何ですか.3台の携帯電話を落として、最後にテストしてから、耐投指数に必要な最低テスト回数を測定することができます.
では、この最小のテスト回数を見つける方法を考えてみましょう.ここでは、このテスト回数をk回とし、3台の携帯電話で合計k回テストして耐投指数を測定することができます.k回の機会がある以上、1台目の携帯電話をまずk階から落としてもいいです.1台目の携帯電話が落ちて死んだら、2台目の携帯電話はk-1回の機会を残して、1 k-1階からテストすることができます.もし1台目の携帯電話が死んでいなければ、k-1回のチャンスが残っていたら、私たちは今度k+(k-1)階から落ちることができます.今回転んで死んだら、2台目の携帯電話にはk-2回のチャンスがあり、k+1 k+(k-1)-1階からテストすることができます.1台目の携帯電話がk+(k-1)層に落ちても生きていれば、k-2回目のチャンスがあり、次はk+(k-1)+(k-2)層から落ちることができます.このように、k回以内に耐投指数を測定できるに違いない.
では、誰かが言います.あなたはここで2台の携帯電話しか話していませんが、私たちは3台の携帯電話を持っています.実は状況は同じです.もし私たちがn台の携帯電話のm階を持っていて、1台目の携帯電話がk階で転んで死んだら、次はn-1台の携帯電話のk-1階の状況をテストします.もし転んでいなければ、n台の携帯電話のm-k階をテストする場合(階が高いほど落ちやすくなるという主観的な意識がありますが、それは必ずしもそうではありません.携帯電話も1000階まで落ちて死なない可能性がありますので、テストの場合は階数だけを見ることができます.k+1 mと1 m-kは同じです).
以上より,動的移動方程式を提案することができる:dp[i][j]はi部携帯電話j階の最小テスト回数を表し,dp[i][j]=max(dp[i-1][k-1],dp[i][j-k])+1,k∈[1,j-1](ここでmaxを取るのはi台の携帯電話j階にdp[i][j]回のテスト機会があるため、この回数内にすべての状況の耐投指数が測定されることを確保しなければならない.小さいものを取ったら、それより回数が多い場合はテストされることを確保できない).私たちは最初にdp配列を初期化するときに、すべてその最悪の状況に初期化することができ、j階の最悪のテスト回数はj回であり、各階ごとに1回落ちるので、ここで最適な戦略を使った後、回数はこの値以下であるべきであり、方程式はdp[i][j]=min(dp[i][j],max(dp[i-1][k-1],dp[i][j-k])+1)、k∈[1,j-1]に変化することができる.
考え方2:手算.
続けてみましょう.n台の携帯電話のm階は最も少ないk回のテストで耐投指数を測定しなければなりません.私たちは事前にこの耐投指数がどれだけなのか分かりません.つまり、このm階の各階(耐投指数)の状況がこのk回でテストできるので、問題はn台の携帯電話のk回のテストで最も多くの階を測定できることに変わります.
まず数字を小さくして、2台の携帯電話で分析しました.いつものように、第1部はまず第k層から落ちて、死んだら第2部は1~k-1層からテストして、このような状況は明らかに最も多くありません.では、1台目の携帯電話が無傷であれば、k-1回のチャンスがあります.次はk+(k-1)階から落ちることができます.ここでは、1回目の転んでk階をテストしました.2回目の転んでも大丈夫なら、k+(k-1)階をテストしました.
測定できる最大フロアがテーマが与えたフロアm以上であれば、この回数kを求めることができる.
2台の携帯電話の状況はよく理解できますが、次に3台の携帯電話のk回のテストの状況を分析して、少し複雑です.以上の推論によれば,2台の携帯電話k−1回の機会でフロアを測定できることが分かった.今3台の携帯電話、第1台の携帯電話は第層から落ちて、もし転んで死んだら、残りの2台の携帯電話は1~層のテストに対して、もし転んでいなければ、第層から転んで、上と差が少ない道理で、それから式を得ます:
テーマは1000階建てで、kの最小は19です.
以上はこの大物が書いたものだ.https://blog.csdn.net/ryo_218/article/details/79810705
メモ:1.n部の携帯電話はm階のビルをテストして最低のテスト回数の問題を求めてこのようなdp方程式に転化することができます
このうちi部の携帯電話はj階建てをテストし、耐投属性はkであり、1回目のk階建てが割れた場合、i-1部の携帯電話だけがk-1階建てを最初からテストし、割れていなければ、i部の携帯電話はj-k階建てをテストし続け、2つの状況で最大のテスト回数を取得し、k階建てのテストを加え、最後に初期化されたdp値を更新する.2.dp初期化はできるだけ少なく、必ず正確に、一度だけ初期化することができ、できるだけn個の値を一度に初期化できるか、0と1の特殊な値を選択することができる.
x星の住民は性格が悪いが、彼らが怒っている間に唯一の異常な行動は携帯電話を落とすことだ.
各メーカーも、耐投型携帯電話を次々と発売している.x星の品質監督局は、携帯電話が耐投試験を経なければならないことを規定し、耐投指数を評価してから、上場流通を許可した.
x星には雲にそびえる高い塔がたくさんあり、ちょうど耐投テストに使えます.塔の各層の高さは同じで、地球とは少し違いますが、彼らの最初の層は地面ではなく、私たちの2階に相当します.
携帯電話が7階から落ちても壊れなかったが、8階が壊れた場合、携帯電話の耐投指数=7になる.
特に、携帯電話が1階から落ちて壊れてしまうと、耐投指数=0になります.
タワーの最上階のn階に着いて投げて壊れなかったら、耐投げ指数=n
テスト回数を減らすため、メーカーごとに3台の携帯電話をサンプリングしてテストに参加する.
あるテストの塔の高さは1000階で、もし私たちがいつも最適な戦略を採用すれば、最悪の運の下で最大何回テストして携帯電話の耐投指数を確定する必要がありますか?
この最大テスト回数を記入してください.
注意:記入する必要があるのは整数で、余分な内容を記入しないでください.
答え:19
構想1:ダイナミックプランニング.
まず、もう一度問題を見てみましょう.メーカーごとに3台の携帯電話をサンプリングしてテストに参加します.あるテストの塔は1000階建てです.もし私たちがいつも最善の戦略を採用していたら、最悪の運の下で最大何回テストしなければ携帯電話の耐投指数を確定できませんか.ベスト・ポリシーとは何ですか.最悪の運の下とは何ですか.3台の携帯電話を落として、最後にテストしてから、耐投指数に必要な最低テスト回数を測定することができます.
では、この最小のテスト回数を見つける方法を考えてみましょう.ここでは、このテスト回数をk回とし、3台の携帯電話で合計k回テストして耐投指数を測定することができます.k回の機会がある以上、1台目の携帯電話をまずk階から落としてもいいです.1台目の携帯電話が落ちて死んだら、2台目の携帯電話はk-1回の機会を残して、1 k-1階からテストすることができます.もし1台目の携帯電話が死んでいなければ、k-1回のチャンスが残っていたら、私たちは今度k+(k-1)階から落ちることができます.今回転んで死んだら、2台目の携帯電話にはk-2回のチャンスがあり、k+1 k+(k-1)-1階からテストすることができます.1台目の携帯電話がk+(k-1)層に落ちても生きていれば、k-2回目のチャンスがあり、次はk+(k-1)+(k-2)層から落ちることができます.このように、k回以内に耐投指数を測定できるに違いない.
では、誰かが言います.あなたはここで2台の携帯電話しか話していませんが、私たちは3台の携帯電話を持っています.実は状況は同じです.もし私たちがn台の携帯電話のm階を持っていて、1台目の携帯電話がk階で転んで死んだら、次はn-1台の携帯電話のk-1階の状況をテストします.もし転んでいなければ、n台の携帯電話のm-k階をテストする場合(階が高いほど落ちやすくなるという主観的な意識がありますが、それは必ずしもそうではありません.携帯電話も1000階まで落ちて死なない可能性がありますので、テストの場合は階数だけを見ることができます.k+1 mと1 m-kは同じです).
以上より,動的移動方程式を提案することができる:dp[i][j]はi部携帯電話j階の最小テスト回数を表し,dp[i][j]=max(dp[i-1][k-1],dp[i][j-k])+1,k∈[1,j-1](ここでmaxを取るのはi台の携帯電話j階にdp[i][j]回のテスト機会があるため、この回数内にすべての状況の耐投指数が測定されることを確保しなければならない.小さいものを取ったら、それより回数が多い場合はテストされることを確保できない).私たちは最初にdp配列を初期化するときに、すべてその最悪の状況に初期化することができ、j階の最悪のテスト回数はj回であり、各階ごとに1回落ちるので、ここで最適な戦略を使った後、回数はこの値以下であるべきであり、方程式はdp[i][j]=min(dp[i][j],max(dp[i-1][k-1],dp[i][j-k])+1)、k∈[1,j-1]に変化することができる.
考え方2:手算.
続けてみましょう.n台の携帯電話のm階は最も少ないk回のテストで耐投指数を測定しなければなりません.私たちは事前にこの耐投指数がどれだけなのか分かりません.つまり、このm階の各階(耐投指数)の状況がこのk回でテストできるので、問題はn台の携帯電話のk回のテストで最も多くの階を測定できることに変わります.
まず数字を小さくして、2台の携帯電話で分析しました.いつものように、第1部はまず第k層から落ちて、死んだら第2部は1~k-1層からテストして、このような状況は明らかに最も多くありません.では、1台目の携帯電話が無傷であれば、k-1回のチャンスがあります.次はk+(k-1)階から落ちることができます.ここでは、1回目の転んでk階をテストしました.2回目の転んでも大丈夫なら、k+(k-1)階をテストしました.
測定できる最大フロアがテーマが与えたフロアm以上であれば、この回数kを求めることができる.
2台の携帯電話の状況はよく理解できますが、次に3台の携帯電話のk回のテストの状況を分析して、少し複雑です.以上の推論によれば,2台の携帯電話k−1回の機会でフロアを測定できることが分かった.今3台の携帯電話、第1台の携帯電話は第層から落ちて、もし転んで死んだら、残りの2台の携帯電話は1~層のテストに対して、もし転んでいなければ、第層から転んで、上と差が少ない道理で、それから式を得ます:
テーマは1000階建てで、kの最小は19です.
以上はこの大物が書いたものだ.https://blog.csdn.net/ryo_218/article/details/79810705
import java.util.*;
public class Main{
public static int phone = 3,floor = 1000;
public static int[][] dp = new int[5][1100];
public static void main(String[] args){
for(int i=1;i<=phone;i++){
for(int j=1;j<=floor;j++){
dp[i][j] = j;
}
}
for(int i=2;i<=phone;i++){
for(int j=1;j<=floor;j++){
for(int k=1;k<=j-1;k++){
dp[i][j]=Math.min(dp[i][j],Math.max(dp[i-1][k-1],dp[i][j-k])+1);
}
}
}
System.out.println(dp[3][1000]);
}
}
メモ:1.n部の携帯電話はm階のビルをテストして最低のテスト回数の問題を求めてこのようなdp方程式に転化することができます
dp[i][j]=min(dp[i][j],max(dp[i-1][k-1],dp[i][j-k])+1)
このうちi部の携帯電話はj階建てをテストし、耐投属性はkであり、1回目のk階建てが割れた場合、i-1部の携帯電話だけがk-1階建てを最初からテストし、割れていなければ、i部の携帯電話はj-k階建てをテストし続け、2つの状況で最大のテスト回数を取得し、k階建てのテストを加え、最後に初期化されたdp値を更新する.2.dp初期化はできるだけ少なく、必ず正確に、一度だけ初期化することができ、できるだけn個の値を一度に初期化できるか、0と1の特殊な値を選択することができる.