ac

思路

记问题为P(n, k)，在最差的情况下扔的最小次数

n == 0, 不用管
k == 1, 必须从第1层尝试到第n层

假设棋子从i层扔
1. 碎了(少了一个棋子)， P(n, k) 变成 P(n-i, k-1)
2. 没有碎, P(n, k) 变成 P(i-1, k)

即有, 从i层扔下
1 + Max( P(n-i, k-1), P(i-1, k) )

i, n-i 确保范围是[1, n], 最后
P(n, k) = 1 + Min (  Max( P(n-i, k-1), P(i-1, k) ) )

可以反过来问：K个棋子，扔M次，可以试出多高楼层

常规动态规划

空间 n * k
时间 n * k * n

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int kChess = sc.nextInt();

        int[][] dp = new int[n+1][kChess+1];
        for(int i=0;i<=kChess;i++){
            dp[0][i] = 0;
        }
        // 只有一层
        for(int i=0;i<=kChess;i++){
            dp[1][i] = 1;
        }
        // 只有1个棋子
        for(int i=1;i<=n;i++){
            dp[i][1] = i;
        }
        // 2～n层
        for(int i=2;i<=n;i++){
            // 2～kChess个棋子
            for(int j=2;j<=kChess;j++){
                int minVal = Integer.MAX_VALUE;
                for(int k=1;k<=i;k++){
                    int tmp = Math.max(dp[i-k][j-1], dp[k-1][j]);
                    minVal = Math.min(minVal, tmp);
                }
                dp[i][j] = minVal + 1;
            }
        }
        System.out.println(dp[n][kChess]);
    }

}
/*
P(n, k) = 1 + Min (  Max( P(n-i, k-1), P(i-1, k) ) )

3 2
2

p\k
   1  2
0  0  0
1  1  1
2  1
3  1
 */

四边形不等式

例子： 3个棋子在解决100层楼时，第1个棋子仍在37层楼时最终导致了最优解。那么2个棋子在解决100楼层时，第1个棋子也不需要去试37层楼以上的楼了，只需要试37及其以下的。

例子： 2个棋子在解决10层楼时，第1个棋子仍在4层楼时最终导致了最优解。那么2个棋子在解决11层或者更多楼层时(比如100层)，第1个棋子也不需要去试1、2、3层楼，只用从4层及其以上的楼层去试即可。

结论：

求出了k个棋子在解决n层楼时的最小步骤(dp[n][k]),那么如果在这个尝试过程中发现，第一个棋子在m层楼的这种尝试最终导致了最优解。则在求k个棋子在解决n+1层楼时(dp[n+1][k]),不需要去尝试m层以下的楼。
求出了k个棋子在解决n层楼时的最小步骤(dp[n][k]),那么如果在这个尝试过程中发现，第一个棋子仍在m层楼的这种尝试最终导致了最优解。则在求小于k个棋子在解决n层楼时(dp[n][1...k-1]),不需要去尝试m层以上的楼。

四边形不等式可以将时间复杂度从O(N^3)降到O(N^2)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int kChess = sc.nextInt();
        System.out.println(solution(n, kChess));
    }

    static int solution(int n, int kChess){
        if(n < 1 || kChess < 1){
            return 0;
        }
        if(kChess == 1){
            return n;
        }
        int[][] dp = new int[n+1][kChess+1];
        for(int i=0;i<=kChess;i++){
            dp[0][i] = 0;
        }
        // 只有一层
        for(int i=0;i<=kChess;i++){
            dp[1][i] = 1;
        }
        // 只有1个棋子
        for(int i=1;i<=n;i++){
            dp[i][1] = i;
        }
        // 存储n-1是的最优解，供解决n问题用，初始 k=1 的最优解
        int[] cands = new int[n + 1];
        for(int i=1;i<=n;i++){
            cands[i] = 1;
        }
        // 2～n层
        for(int i=2;i<=n;i++){
            // 解决n=i问题，0...i-1问题已经解决了
            for(int j = kChess; j > 1;j--){
                int minVal = Integer.MAX_VALUE;
                int minEnum = cands[j];
                int maxEnum = j == kChess ? i / 2 + 1: cands[j] + 1;
                for(int k=minEnum;k<=maxEnum;k++){
                    int curr = Math.max(dp[k-1][j-1], dp[i-k][j]);
                    if(curr < minVal){
                        minVal = curr;
                        cands[j] = k;
                    }
                }
                dp[i][j] = minVal + 1;
            }
        }
        return dp[n][kChess];
    }
}
/*
3 2
2

105 2
14
 */

换个思路ac

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int kChess = sc.nextInt();
        System.out.println(solution(n, kChess));
    }

    static long solution(int n, int kChess){
        if(n < 1 || kChess < 1){
            return 0;
        }
        if(kChess == 1){
            return n;
        }
        // dp[i] 表示i个棋子可以试出来的最高层，最开始扔0次，都是0
        int[] dp = new int[kChess + 1];
        long step = 0;
        while (dp[kChess] < n) {
            for (int i = kChess; i > 0; i--) {
                dp[i] = dp[i] + dp[i-1] + 1; // 没有碎，碎了，试的那层
            }
            ++step;
        }
        return step;
    }
}
/*
i个棋子扔j次，能试出来的最高层
dp[i][j] = dp[i][j-1] + dp[i-1][j-1] + 1

扔第一个棋子在a层
* 碎了，向下看 i-1个棋子扔 j-1次 能得到多少层
* 没有碎，看上看 i个棋子扔 j-1次 能得到多少层

3 2
2

105 2
14
 */