Acwing.4741 魔法百合井(动态规划)

题目

森林里有一口很深的魔法井，井中有 L 朵百合花。

你带着一个大空篮子和足够多的硬币来到了井边。

这个井有魔力，向里面投入硬币可以发生神奇的事情：

如果你向井里一次性投入 1 个硬币，井就会发动魔法，将一朵百合花扔进你的篮子里。
如果你向井里一次性投入 4 个硬币，井就会发动魔法，统计并记录到目前为止，已经扔进你的篮子里的百合花的数量。
如果你向井里一次性投入 2 个硬币，井就会发动魔法，将等同于上次记录数量的百合花扔进你的篮子里。
有一点需要特别注意，如果你向井里一次性投入 1 个或 2 个硬币后，井中已经没有足够的百合花扔给你了，那么井就不会发动任何魔法，也不会扔给你任何百合花（钱白花了）。

请你计算，为了将所有百合花都收入篮中，所需要花费的最少硬币数量。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据占一行，包含一个整数 L，表示井中百合花的总数量。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y，其中 x 为组别编号（从 1 开始），y 为需要花费的最少硬币数量。

数据范围

1≤T≤100,
1≤L≤105

• 输入样例：

2
5
20
1
2
3

• 输出样例：

Case #1: 5
Case #2: 15
1
2

样例解释

对于 Case 1，井中一共有 5 朵百合花。

最佳方案是一个接一个的连续向井中投入 5 个硬币，这样我们可以一个接一个的得到 5 朵百合花。

一共需要花费 5 个硬币。

对于 Case 2，井中一共有 15 朵百合花。

最佳方案为：

首先，一个接一个的连续向井中投入 5 个硬币，这样我们可以一个接一个的得到 5 朵百合花。
然后，我们一次性向井中投入 4 个硬币，这样井会记录下到目前为止扔进我们篮中的百合花数量为 5。
最后，我们重复三次，每次向井中投入 2 个硬币，这样每次都可以得到 5 朵百合花，从而得到剩余的全部 15 朵百合花。
一共需要花费 15 个硬币。

题解

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author akuya
 * @create 2023-10-11-10:54
 */
public class well {
    static int L=100010;
    static int dp[]=new int[L];
    static int top=6;
    public static void main(String[] args) {
        Arrays.fill(dp,Integer.MAX_VALUE);
        Scanner scanner=new Scanner(System.in);
        int t=scanner.nextInt();
        int T=t;
        for(int i=1;i<=6;i++)dp[i]=i;
        while(t--!=0){
            int l=scanner.nextInt();
            int pos=T-t;
            if(l>top){
                for(int i=top+1;i<=l;i++){
                    if(i%2==0){
                        int s=findFactors(i);
                        dp[i]= Math.min(dp[i-1]+1,s);
                    }else{
                        int s=findFactors(i);
                        dp[i]=Math.min(dp[i-1]+1,s);
                    }
                }
                top=l;
                System.out.print("Case #"+pos+": ");
                System.out.println(dp[l]);
            }else{
                System.out.print("Case #"+pos+": ");
                System.out.println(dp[l]);
            }

        }
    }

    public static int findFactors(int n) {
        int res=Integer.MAX_VALUE;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                res=Math.min(res,dp[i]+4+((n-i)/i)*2);
                if (i != n / i) {
                    res=Math.min(res,dp[n/i]+4+((n-n/i)/(n/i))*2);
                }
            }
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

思路

这种多种变化得到目标的题目，都可以考虑使用动态规划
根据题目要求
传递方程为 dp[i-1] 与 dp[i的因数]+4+（i/因数-1）*2 的最大值
即可得出答案。