当前位置：首页 > article >正文

蓝桥杯算法心得——想吃冰淇淋和蛋糕（dp）

article 2025/2/24 19:26:48

大家好，我是晴天学长，dp题，怎么设计状态很重要，需要的小伙伴可以关注支持一下哦！后续会继续更新的。💪💪💪

1) .想吃冰淇淋和蛋糕

在这里插入图片描述
想吃冰淇淋与蛋糕
输入格式
第一行输入一个整数n。代表天数。
第二行输入一个序列a,代表吃蛋糕每天提供的快乐值。
第三行输入一个序列b,代表吃冰淇淋每天提供的快乐值。
输出格式
输出获得的快乐值总和最大的值。
样例输入
3
3 4 4
2 2 1
样例输出
10
说明你可以第一天吃冰淇淋, 第二天吃蛋糕，第三天吃蛋糕，最终是2+4+4=10. 你不能选择3, 4,4,因为无法连续天玩同一款游戏。
评测数据规模
1≤n≤10,1≤ai,bi< 10*.

2) .算法思路

想吃冰淇淋与蛋糕
1.有4个状态。
（1）连续吃蛋糕一天
（2）连续吃蛋糕两天
（3）连续吃冰淇淋一天
（4）连续吃冰淇淋两天
2.建立一个二维的dp数组
3.遍历n。

3）.算法步骤

1.读取输入的数据，包括蛋糕和冰淇淋的数量以及它们的价值。
2.创建一个二维数组dp，用于存储中间结果。dp[i][j]表示在第i个位置选择了蛋糕或冰淇淋后，所能获得的最大价值。
3.初始化dp数组的第一行。根据题目要求，第一个位置可以选择蛋糕或冰淇淋，因此将其价值赋给dp[0][0]和dp[0][1]，同时将冰淇淋的价值赋给dp[0][2]和dp[0][3]。
4.从第二行开始，遍历每个位置和选择。对于第i个位置和第j个选择，根据题目给出的规则，更新dp[i][j]的值。
（1）如果j等于0，表示选择了蛋糕，并且前一个位置选择了冰淇淋，所以dp[i][j]等于前一个位置选择冰淇淋的最大价值加上当前蛋糕的价值。
如果j等于1，表示选择了蛋糕，并且前一个位置也选择了蛋糕，所以dp[i][j]（2）等于前一个位置选择蛋糕的最大价值加上当前蛋糕的价值。
如果j等于2，表示选择了冰淇淋，并且前一个位置选择了蛋糕，所以dp[i][j]（3）等于前一个位置选择蛋糕的最大价值加上当前冰淇淋的价值。
（4）如果j等于3，表示选择了冰淇淋，并且前一个位置也选择了冰淇淋，所以dp[i][j]等于前一个位置选择冰淇淋的最大价值加上当前冰淇淋的价值。
5.遍历完所有位置和选择后，找到dp数组最后一行的最大值，即为所求的最大价值。
6.输出最大价值。

4）. 代码实例

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(System.out);
    static String[] lines;

    public static void main(String[] args) throws IOException {
        lines = in.readLine().split(" ");
        int n = Integer.parseInt(lines[0]);
        int[] dangao = new int[n];
        int[] bingqiling = new int[n];
        lines = in.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            dangao[i] = Integer.parseInt(lines[i]);
        }
        lines = in.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            bingqiling[i] = Integer.parseInt(lines[i]);
        }
        int[][] dp = new int[n][4];
        dp[0][0] = dangao[0];
        dp[0][1] = dangao[0];
        dp[0][2] = bingqiling[0];
        dp[0][3] = bingqiling[0];

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 4; j++) {
                if (j == 0) {
                    dp[i][j] = Math.max(dp[i - 1][2], dp[i - 1][3]) + dangao[i];
                }
                if (j == 1) {
                    dp[i][j] = dp[i - 1][0] + dangao[i];
                }

                if (j == 2) {
                    dp[i][j] = Math.max(dp[i - 1][0], dp[i - 1][1]) + bingqiling[i];
                }

                if (j == 3) {
                    dp[i][j] = dp[i - 1][2] + bingqiling[i];
                }
            }

        }
        long max = Integer.MIN_VALUE;
        for (int i = 0; i < 4; i++) {
            max = Math.max(max, dp[n - 1][i]);
        }
        out.println(max);
        out.flush();
        out.close();
    }
}