UVA 10934&&ブルーブリッジカップテスト回数&&イーグル問題

UVA 10934&&ブルーブリッジカップ::テスト回数&&鷹卵問題

以上の3つの問題はすべて1つの問題に属して、ここで私は鷹の卵の問題を例にして分析します
参考サイト:http://datagenetics.com/blog/july22012/index.html
この編だけが私のすべての問題を完全に解釈した.
ここでは、ダイナミックプランニングのソリューションについてのみ説明します.辛抱強く読んでください
f[e][k]f[e][k]f[e][k]は、e e e卵k k階が答えを見つけた最小テスト回数を表す.

仮に私が今回のテストで1～k目のi i i層に卵を投げたとします.では、2つの状況に分けます.

第i i i層の卵が割れていない場合、強靭度は[i+1,k][i+1,k][i+1,k]のうち、すなわちk−i k−i個の連続する層の間に、現在、私はe−1 e−1 e−1 e−1個の卵を持っているので、問題はf[e−1][k−i]f[e−1][k−i]f[e−1][k−i]f[e−1][k−i]f[e−1][k−i]に帰結する.すなわちf[e][k]=f[e−1][k−i]+1 f[e][k]=f[e−1]][k−i]+1 f[e][k]=f[e−1]][k−i]+1

第i i i層の卵が割れていなければ、強靭度は[1,i−1][1,i−1][1,i−1][1,i−1]の間、すなわちi−1 i−1 i−1 i−1連続の層の間に、現在私にはe個の卵があるので、問題はf[e][i−1]f[e][i−1]f[e][i−1]f[e][i−1]f[e][k]=f[e][i][i−1]+1 f[e][k]=f[e][i][i−1]+1 f[e][k]=f[e][e][i−1]=f[e][i−1]+1 f[e][k]=f[e

この問題は運の問題であるため、制御不能であり、要求が最悪の場合であるため、f[e][k]=m a x(f[e−1][i−1],f[e][k−i])+1 f[e][k]=max(f[e−1][i−1],f[e][k−i])+1 f[e][k]=max(f[e−1][i]=max(f[e−1][i],f[e][k−i])+1

上からe e e個の卵k k層があり、i i i層目に卵を投げるのに必要な最小テスト回数を見つけた(Remember we need to mimimimimize the number of drops in the worst case)
運はコントロールできないが、私たちが選んだi i iはコントロールできるので、私たちはすべてのiを遍歴して、f[e][k]f[e][k]f[e][k]f[e][k]の中で最も小さいものを選ぶことができる.
繰返し式f[e][k]=m i n(m a x(f[e−1][i−1],f[e][k−i])+1)),i∈[1,k]f[e][k]=min({~max(f[e−1][i−1],f[e][k−i]}+1)),iin[1,k]f[e][k]=min(max(f[e−1][i−1],f[e][k−i])+1)),i∈[1,k]
コードメモリ検索
コード:

#include
using namespace std;
const int inf=0x3f3f3f3f;
int f[1010][1010];
bool iscal[1010][1010];
void init(){
    memset(iscal,false,sizeof(false));
}
int F(int e,int k){
    if(k==0)
        return 0;
    if(e==0)
        return inf;//e=0 k>0  
    if(iscal[e][k])
        return f[e][k];
    int minn=inf;
    for(int i=1;i<=k;++i){
            minn=min(minn,max(F(e-1,i-1),F(e,k-i))+1);
    }
    iscal[e][k]=true;
    return f[e][k]=minn;
}
int main(){
    int e,k;
    init();
    while(~scanf("%d %d",&e,&k)){
        cout<<F(e,k)<<endl;
    }
    return 0;
}