卵が落ちる---クラシックdp(ダイナミックプランニング)

タイトル:

n個の卵と1 mからm階建ての建物をあげます.
卵の耐落下度をテストする必要があります.つまり、卵が何層目から投げられても割れます.
卵の耐落下度がFであれば、Fより高い階から落ちた卵は砕け、F階やそれより低い階から落ちた卵は破れない.
テストのたびに卵を1つ持って、任意の高さのフロアから捨てることができます(割れていなければ使い続けることができます)
あなたの目標はFの値がいくらなのかをテストすることです.  
 

問題解決の考え方：

1、まず私たちはテーマの意味を理解しなければなりません.テーマの意味によって、私たちは簡単に任務を完成する愚かな方法を考えます.それは卵を持って、1階からゆっくりと上層部にテストすることです.この方法は卵1個で耐転度を見つけることができる.しかし、必要なテスト回数は最大N(N層も割れなければn回必要)です.
2、どのように回数を最適化しますか?二分検索を連想しやすいかもしれませんが、
100階建てのビルがあると仮定して、卵を2つあげます.
二分で検索すると、まず50階に投げ、卵が割れなければ75階に投げます.もし50階が割れたら、卵が1つしか残っていないので、波をかけることはできません.最初の考えを使って、1階からゆっくり上を探して、臨界階を見つけることができることを保証することができます.
タイトルでは、最悪の場合の最小回数を考慮すると、二分で検索すると、最悪の場合、臨界層数が49層であれば50回試してみます.この方法は最も優れた方法ではない.

3、dp

先に情況を仮定します:2つの卵、100階建てのビル、 ， を求めます
答えはxだと仮定します.(最悪x回必要です)
まずx層目に卵を投げると2つの結果が得られます
1、割れたら残りの1個の卵を1-(x-1)から遍歴してみるしかない
2、割れていなければ2回目はx+(x-1)フロアで転ぶ.
どうしてx+x-1階なのですか?まずxステップで答えが得られると仮定しましたが、今ではx層で1回使っているので、x-1ステップしか残っていません.
だからx+(x-1)層を選び、割れたらx-2ステップでx+1~x+(x-1)-1のすべてのフロアを巡ることができます.
順次類推する.
x+(x-1)階で割れたら、同じ1、x+1~x+(x-1)-1を遍歴して割れなければ、同じ2、x+(x-1)+(x-2)層で落ちる
.....................................
私たちが増加するたびにフロアが前回減少していることがわかります.増加した層数が0になる前に最上階に着くことを保証しなければなりません
だからあります:x+(x-1)+...+1≧100
等差数列の和を求めた後、x^2+x-200≧0に簡略化することができ、xは14である.
明らかに14は私たちの2分の最悪の状況より50回少ないのが正解です.
 
では、私たちが仮定した問題から飛び出して、一般的な方法を押してみましょう.
n個の卵、m階建て
f[n][m]は ， を表す
状態遷移方程式は,f[n][m]=min{1+max(f[n−1][k−1],f[n][m−k])}kが[1,m−1]に属する.
どうしてそうなの?
内側を見てみましょう
max ( f [ n-1 ][ k-1 ] , f [ n ][ m-k ] )
n個の卵の時、私たちはk番目の層を選んで下に落ちました.
破れたら、手にn-1卵しかないので、f[n-1][k-1]フロアをテストする必要があります.破れていなければ、手にn個の卵があるので、k+1~mのフロアをテストする必要があります.すなわちf[n][m-k]である.
破れても破れても一度テストしたから破れても破れなくても+1
なぜ最大値をとるのでしょうか.問題は最悪だと言っているので、この2つの中で歩数が多いものを取ります.
kはどうやって選んだのか、全体の式を見てみましょう.
f[n][m]=min{1+max(f[n-1][k-1],f[n][m-k])}kは[1,m-1]に属する
kの選択範囲は[1,m-1]であり、テスト回数を最小限に抑えることを目的としているので、結果を最小限に抑えるk値をここで選びます.
 
これで構想全体が完成した
初期話の時に二次元配列全体を最悪に初期化してdpすればいい
ps:max(f[n-1][k-1],f[n][m-k])を補足すると、最大越高層を選ぶ必要がないほど割れやすいので、直接低層を選ぶ人がいる
これは間違っています.確かに上層部ほど割れやすいことに注意してください.しかし、私たちが要求しているのは回数が最小で、割れていないこととは関係ありません.割れていないなら、直接1階から卵を1つで十分です.だから、私たちが要求していることを理解してください.

コード:

#include
#include
#include
#include
#include
using namespace std;
const int INF=0x3f3f3f3f;
int a[105][10005];
int n,m,minn;
int main(){
    for(int i=1;i<=100;i++){// 
        for(int j=1;j<=10000;j++){
            a[i][j]=j;
        }
    }
    scanf("%d%d",&n,&m);//n   m 
    for(int i=2;i<=n;i++){
        for(int j=2;j<=m;j++){
            for(int k=1;k<=j-1;k++){
                a[i][j]=min(a[i][j],1+max(a[i-1][k-1],a[i][j-k]));
            }
        }
    }
    printf("%d
",a[n][m]);
}

参照ドキュメント:
https://blog.csdn.net/wolinxuebin/article/details/47057707
http://www.cnblogs.com/Matrix_Yao/p/4793823.html