当前位置:首页 > 入门组 > 2023年CSP-J 小苹果题解(洛谷P9748) | 动态规划解题思路与代码解析

2023年CSP-J 小苹果题解(洛谷P9748) | 动态规划解题思路与代码解析

1周前 (07-07)

2023年CSP-J 小苹果题解(洛谷P9748) | 动态规划解题思路与代码解析 CSP-J  动态规划 数学推导 第1张

一、题目解读

CSP-J 2023年的小苹果题目(对应洛谷P9748)是一个经典的动态规划问题。题目描述了一个苹果被依次取走的场景:每天取走当前苹果数量的 (n-1)/3 + 1 个苹果,直至全部取完。需要计算两个关键值:总天数和最后一个苹果被取走的天数。该题目考验对循环规律的观察与数学推导能力,需通过编程实现高效的解题逻辑。

二、解题思路

作者提供的代码采用循环模拟与标记法解决该问题。核心思路为:

1. 天数递增与取苹果逻辑:通过循环模拟每天的操作,每次计算取走的苹果数为 (n-1)/3 + 1。

2. 关键节点标记:当剩余苹果数满足 (n-1) % 3 == 0 时,说明当前轮次取走最后一个苹果,记录天数。

3. 动态更新剩余苹果数:通过数学推导优化,避免直接模拟取苹果过程,提升效率。

三、解题步骤解析

1. 初始化变量:

    n 为苹果总数,days 初始化为0,last_day 记录关键天数,found 标记是否找到目标苹果。

2. 循环模拟取苹果过程:

    每天 (days++) 计算取走数量 (n-1)/3 + 1,更新剩余苹果数 n -=...。

3. 判断关键节点:

    当 n-1 为3的倍数时,说明当前取走最后一个苹果,记录天数并标记 found。

4. 终止条件:当 n=0 时,循环结束,输出总天数和关键天数。

四、代码与注释

#include <iostream>  
using namespace std;  

int main() {  
    int n; // 苹果总数  
    cin >> n;  
    int days = 0; // 总天数  
    int last_day = 0; // 第n个苹果被取走的天数  
    bool found = false; // 是否已找到第n个苹果  
    
    while (n > 0) {  
        days++; // 天数增加  
        // 检查当前轮次是否取走第n个苹果  
        if (!found && (n - 1) % 3 == 0) {  
            last_day = days;  
            found = true;  
        }  
        // 计算本轮取走的苹果数:(n-1)/3 + 1  
        n -= ((n - 1) / 3 + 1);  
    }  
    
    cout << days << " " << last_day << endl;  
    return 0;  
}

注释说明:代码通过循环与条件判断,结合数学推导简化计算,高效求解目标天数。

五、总结

该题目通过动态规划思想,将复杂模拟转化为数学逻辑推导。关键点在于识别取苹果的规律(每轮取走 (n-1)/3 + 1 个)和标记最后一个苹果的位置。代码简洁且时间复杂度低,适合竞赛场景。掌握此类问题的解题思路,有助于提升对循环规律与数学优化的理解。


原创内容 转载请注明出处

分享给朋友:

相关文章

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

一:重新解读题目泰波那契数列是一个充满数学趣味的递推序列:从第3项开始,每个数均为前三个数的和(即Tₙ₊₃ = Tₙ + Tₙ₊₁ + Tₙ₊₂)。当给定整数n时,需要高效计算出第n项的值。面对此类递...

2024年GESP五级武器强化(洛谷B4071)解题代码C++版

2024年GESP五级武器强化(洛谷B4071)解题代码C++版

一、题目解读    2024年GESP(青少年软件编程能力等级考试)五级中的“武器强化”(洛谷平台题目编号B4071)是一道典型的算法优化问题。题目要求通过合理...

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

一、题目解读2024年蓝桥杯省B组“传送阵”题目要求处理一个包含n个节点的图,节点间存在单向传输关系。每个节点i可传送至a[i]指定的节点,形成可能存在的环结构。题目需求解从任意节点出发能到达的最长路...

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

一、题目解读LeetCode 120题“三角形最小路径和”要求给定一个由数字组成的三角形,从顶部开始向下移动,每次可向左或向右移动一格,计算从顶至底的最小路径和。三角形以二维向量形式给出,每层元素数量...

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

一、题目解读洛谷P4551题要求在一个无向图中,寻找任意两点路径权值异或后的最大值。题目输入为图的边信息(点数n和n-1条边),每条边包含起点、终点及权值。需输出所有路径中权值异或的最大值。问题核心在...

【蓝桥杯2015省赛解析】生命之树:树形DP解题全攻略(洛谷P8625代码详解)

【蓝桥杯2015省赛解析】生命之树:树形DP解题全攻略(洛谷P8625代码详解)

一、题目解读    “生命之树”是一道经典的树形结构问题,要求计算一棵带权树中,以某个节点为根的最大子树权值和。题目输入为n个节点及边信息,每个节点有权值wi,...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。