UVa 10934-Dropping water balloons(クラシックdp)

タイトルリンク
概要:気球の硬度は1つのn層のビルを借りて気球の硬度を確定して、もし気球が第f層から落ちて、落ちていないならば、気球の硬度が少なくともfであることを説明します;さもなくば気球の硬度がfを超えないことを説明してあなたにk個の気球を実験して、少なくとも何回気球の硬度を確定することができることを求めます(あるいは結論を出します:最上階に立っても破れません)
分析:まず問題を読み、入出力を見てみましょう.
Inputが入力した各行には複数のテストが含まれており、各テストは1行です.各グループのテストは2つの整数kとnを含み、1<=k<=100であり、nは64ビットの整数(間違いなく、この建物は確かに高い)であり、最後のグループk=0、n=0は終了を表し、このテストは処理されない.Outputはテスト毎に、最悪の場合、水球がフロアを破る最小回数を測定します.63回を超えると「More than 63 trials needed.」
出力の制限に気づくには、最悪の場合、何が最悪なのかということが重要です.風船が最上階でも落ちないという問題が転化しました.私たちはk個の風船を使って、何回このビルの最上階までテストする必要がありますか.
私たちはまず風船の個数の制限を気にしない:私たちが無数の風船を持っていると仮定すると、最適な案は必ず2点で、logn回が必要です.
風船が1つしかなかったら?これは悲惨で、私たちは第1階から(結局私たちはこの風船しかありません.もし転んだらGGになります)最悪の場合、私たちはN回実験する必要があります.
これらはすべてテーマを理解するのに役立ちます.本当の問題の解はやはり私たちが非常に巧みな状態を設計する必要があります.私たちは問題を変えて、「k個の風船をあげて、j回をなくして、せいぜい何階目を確定することができますか?」

これにより,i番目の気球をf(i,j)状態で表すことができ,j回目に最も多く決定された層数を失うことができる.

f(i,j)については,最も多くの層を決定できることは知られていないが,初めてx層でボールを決定すると仮定し,ボールが破れた場合,1つのボールと1回投げた費用を費やし,f(i−1,j−1)が決定できる層数を知ることができ,x=f(i−1,j−1)+1 x層でボールが破れなければ,1回投げた費用しかかからず,i個のボールが残り,j−1回で使用できることが分かった.これらで決定できる層数f(i,j−1)
ボールを投げるたびに2つの可能性があり、この2つの可能性は互いに独立しているため、私たちの移動方程式は長いです.

f(i,j)=f(i-1,j-1)+1+f(i,j-1)

しっかり覚えなきゃ~~~

// 
#include
#include
#include
#define ll unsigned long long

using namespace std;

ll f[105][70];
int n;
ll k;

int main()
{
    while (scanf("%d%llu",&n,&k)!=EOF&&n)
    {
        f[0][0]=0;
        int ans=-1;
        for (int j=1;j<=63;j++)
            for (int i=1;i<=n&&ans==-1;i++)
            {
                f[i][j]=f[i-1][j-1]+1+f[i][j-1];
                if (f[i][j]>=k)
                {
                    ans=j;
                    break;
                }
            }
        if (ans==-1) printf("More than 63 trials needed.
");
        else printf("%d
",ans);
    }
    return 0;
}