Comment

yyhseu: 2025-05-28 12:12:53

二分的思路和递推的思路奉上

import java.util.Scanner;

class Main{
    public static Scanner sc=new Scanner(System.in);
    public static int[][] memo=new int [10001][101];

    public static int dfs1(int n,int k){//O(kn^2)
        if(n==1||n==0){
            return n;
        }
        if(k==1){
            return n;
        }
        if(memo[n][k]!=-1){
            return memo[n][k];
        }
        int res=Integer.MAX_VALUE;
        for(int j=1;j<=n;j++){
            int l=dfs1(j-1,k-1);
            int r=dfs1(n-j,k);
            res=Math.min(res,Math.max(l,r)+1);
        }
        memo[n][k]=res;
        return res;
    }
    public static int dfs2(int n,int k){//O(nklogn)
        if(n==0||k==1){
            return n;
        }
        if(memo[n][k]!=-1){
            return memo[n][k];
        }
        int res=Integer.MAX_VALUE;
        int low=1,high=n,mid;
        while(low+1<high){
            mid=low+(high-low)/2;
            int l=dfs2(mid-1,k-1);
            int r=dfs2(n-mid,k);

            if(l<r){
                low=mid;
            }else if(l>r){
                high=mid;
            }else{
                low=high=mid;
            }
        }
        res=1+Math.min(Math.max(dfs2(low-1,k-1),dfs2(n-low,k)),Math.max(dfs2(high-1,k-1),dfs2(n-high,k)));
        memo[n][k]=res;
        return res;
    }
    public static int solve_(int n,int k){
        int[][] f = new int[n + 1][k + 1];
        for (int i = 1; ; i++) {
            for (int j = 1; j <= k; j++) {
                f[i][j] = f[i - 1][j] + f[i - 1][j - 1] + 1;
            }
            if (f[i][k] >= n) {
                return i;
            }
        }
    }
    public static int solve(int n,int k){
        for(int i=0;i<=n;i++){
            for(int j=0;j<=k;j++){
                memo[i][j]=-1;
            }
        }
        return dfs2(n,k);
    }


    public static void main(String[] args) {
        int t;
        t=sc.nextInt();
        while(t-->0){
            int n,k;
            k=sc.nextInt();
            n=sc.nextInt();
            System.out.println(solve_(n,k));
        }
    }
}

harkerhand: 2025-04-25 18:19:40

非常好状态转移

#include <bits/stdc++.h>
using namespace std;
#define int long long

int superEggDrop(int K, int N)
{
    vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));
    int m = 0;
    while (dp[K][m] < N)
    {
        m++;
        for (int k = 1; k <= K; ++k)
        {
            //  dp[k][m - 1]: 鸡蛋没碎，还可以继续试。
            // dp[k - 1][m - 1]: 鸡蛋碎了，鸡蛋减1，楼层减到扔的楼层以下。
            // 加1是当前这层。
            dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
        }
    }
    return m;
}

signed main()
{
    int nums;
    cin >> nums;
    while (nums--)
    {
        int K, N;
        cin >> K >> N;
        cout << superEggDrop(K, N) << endl;
    }
    return 0;
}

200818倪鹏宇: 2020-11-22 21:15:00

个人感觉两个关键的地方：1、鸡蛋如果没摔碎，还能在更高的楼层继续用。2、在正中间的楼层让鸡蛋掉落并不总是最优解TAT

zcw8887: 2020-11-21 13:33:55

直觉的dp做法会超时，这是因为实际上求解了一个比原问题更强的问题，我们得到的结果中包含了更多的信息。
如果一开始没有思路的小伙伴，可以先仔细想一想2-6是怎么用3次实现的，它与1-2的的关系的关系又是什么。