Noi 7627:卵の硬さ

この問題は少し水っぽい.ただのダイナミックな計画です.f[i][j]はi個の卵がj層目から何回か試す必要があることを示している.dp方程式はやはり考えやすい.の通じるだけで、いくつかの卵が何階で投げても同じ戦略でいいです.

#include
#include
#include
using namespace std;
int f[110][110];
int main() {
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF) {
        memset(f,0,sizeof(f));
        if(m==1) {
            printf("%d
",n);
            continue;
        }
        for(int i=1;i<=100;i++) {   
            f[i][1]=i;
            for(int j=2;j<=10;j++) {
                f[i][j]=i;
                for(int k=2;k<=i;k++)
                    f[i][j]=min(f[i][j],max(f[k-1][j-1],f[i-k][j])+1);
            }
        }
        printf("%d
",f[n][m]);
    }
    return 0;
}