PDD2024.6.16 服务端实习 的一道笔试题

题目描述

某个人打算接下来$n$天吃汉堡，每个汉堡的价格为$p_i$，如果累计消费$100$元，可以获得一张兑换券，可以免费吃一次汉堡，计算第n天的最小的花费。多组测试数据，第一行为T,每组测试数据第一行为n，接下来n行为第i的汉堡价格 $p_i$, 以此类推

样例

1
6
15
25
35
45
55
65

算法1

(动态规划) $O(n*最大可能的兑换卷数量)$

搜索超时，用动态规划解决

java 代码

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author alien
 * @program ac
 * @description
 * 题目描述：
 *
 * @date 2024/6/16$
 */
public class Question2 {
    static int T;
    static int n;
    static int[] p = new int[1010];

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        T = scanner.nextInt();
        for(int tt = 0; tt < T; tt ++ ) {
            n = scanner.nextInt();
            for (int i = 1; i <= n; i ++ ) {
                p[i] = scanner.nextInt();
            }
            problem();
        }
    }

    static void problem() {
        // dp[i][j] 第i天，持有j张兑换卷的情况下的最小花费
        long maxCoupons = 0;
        for (int i = 1; i <= n; i ++ ) {
            maxCoupons += p[i];
        }
        maxCoupons = (long) Math.ceil(maxCoupons / 100.0);  // 可能获得的最大兑换卷数
        int[][] dp = new int[1010][(int) maxCoupons + 1];
        for (int i = 0; i < dp.length; i ++ ) Arrays.fill(dp[i], Integer.MAX_VALUE);
        dp[0][0] = 0;

        for (int i = 1; i <= n; i ++ ) {
            for (int j = 0; j <= maxCoupons && dp[i-1][j] != Integer.MAX_VALUE; j ++ ) {
                dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + p[i]);
                if (dp[i-1][j] < Integer.MAX_VALUE) {
                    int rest = dp[i-1][j] % 100 + p[i];
                    if (rest >= 100) dp[i][j+1] = dp[i-1][j] + p[i];
                }
                if (j + 1 <= maxCoupons && dp[i-1][j + 1] < Integer.MAX_VALUE) {

                    if (dp[i][j] > dp[i-1][j+1]) {
                        dp[i][j] = dp[i-1][j+1];
                    }
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i <= maxCoupons; i ++ ) {
            res = Math.min(res, dp[n][i]);
        }
        System.out.println(res);
    }
}