记录149#includebits/stdc.h using namespace std; #define ll long long // 数据范围到10^5累加后可能爆int必须开long long int main() { ios::sync_with_stdio(false); // 加速IO cin.tie(0); int n; cinn; ll sum0,ans0,a; for (int i1;in;i) { cina; suma; // 实时计算前缀和 // 只有前缀和大于0且不是第一张牌至少合并2张时才加入总分 if (i!1sum0) anssum; } coutans\n; return 0; }题目传送门https://www.luogu.com.cn/problem/P6625前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的贪心算法与前缀和结合的问题。问题转化前缀和视角题目要求我们每次选取“最左边的连续若干张卡牌”进行合并。这意味着无论我们怎么操作本质上都是在不断地选取数组的前缀。假设我们第一次合并了前 i 张卡牌那么这次操作对总分的贡献就是前 i 张卡牌的和即前缀和 Si​ 。合并后这 i 张卡牌变成了一张分值为 Si​ 的新卡牌位于最左端。如果我们接下来继续合并前 j 张卡牌包含刚才合并出的那张新卡牌这次操作对总分的贡献本质上就是原数组前 j 张卡牌的和即前缀和 Sj​ 。因此整个游戏过程的总分实际上就是我们选取的若干个“前缀和”的累加。算法设计贪心策略既然总分等于我们选出的前缀和之和为了让总分最大我们只需要遵循一个简单的贪心原则只要当前的前缀和是正数我们就把它合并进来因为正数会让总分变大。如果当前的前缀和是负数或零合并它只会让总分不变或减少我们就应该立刻停止游戏。注意题目限制“至少合并2张卡牌”所以我们从第2张卡牌开始判断前缀和是否为正。代码分块详细解释1. 头文件与变量定义#includebits/stdc.h using namespace std; #define ll long long // 数据范围到10^5累加后可能爆int必须开long long int main() { ios::sync_with_stdio(false); // 加速IO cin.tie(0); int n; cin n; ll sum 0, ans 0, a;详细分析卡牌的分值 aiai​ 绝对值最大可达 10^5卡牌数量 nn 最大也是 10^5 。在极端情况下前缀和的累加可能会达到 10^10 的级别这远远超过了int类型的表示范围约 2×10^9 。因此代码中定义了ll(long long) 来存储前缀和sum和最终答案ans这是防止数据溢出的关键。2. 核心逻辑线性扫描与贪心累加for (int i 1; i n; i) { cin a; sum a; // 实时计算前缀和 // 只有前缀和大于0且不是第一张牌至少合并2张时才加入总分 if (i ! 1 sum 0) ans sum; } cout ans \n; return 0; }详细分析这是代码的灵魂所在仅用一个循环就解决了问题。实时前缀和在读取每一个卡牌分值a的同时立刻将其累加到sum中。此时的sum就代表了原数组从第 1 张到第i张卡牌的总和。贪心判定if (i ! 1 sum 0)包含两个核心条件。i ! 1满足了题目“至少选取2张卡牌”的硬性约束sum 0则是贪心策略的体现。只要当前累积的前缀和是正收益我们就执行这次合并操作将sum加到总分ans中。为什么不需要复杂的模拟因为无论中间合并了多少次下一次合并最左侧卡牌时其分值总和永远等于当前遍历到的位置的前缀和。我们只需要一路向右扫描遇到正的前缀和就“吃掉”遇到负的前缀和就“停手”后续的负前缀和不会再被加入ans这样就能保证得到的ans是全局最大值。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点数据类型#define ll long long使用 64 位整数存储累加和防止在卡牌数量与分值均达到 105105 时总分计算发生整型溢出前缀和计算sum a在读取数据的同时计算前缀和将复杂的“卡牌合并与替换”过程转化为直观的数学前缀和累加规则约束i ! 1限制从第2张卡牌开始判断严格遵守了题目中“每次至少选取2张卡牌”的操作限制贪心策略sum 0仅当当前前缀和为正时才累加保证了每一步操作都能使总分增加从而获得全局最优解答案累加ans sum将正收益的前缀和计入总分完美模拟了多次合并操作对总分的贡献无需真正修改卡牌序列