AtCoder Beginner Contest竞赛题解 | 洛谷 AT_abc438_d Tail of Snake

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：AtCoder Beginner Contest竞赛题解 | 汇总

【题目来源】

洛谷：AT_abc438_d Tail of Snake - 洛谷

【题目描述】

Snuke 正在观察一条蛇，他很好奇蛇的头部、蛇身和蛇尾分别是哪个部分。他把蛇分成了N NN块，并评估了每个块的头部相似度、身体相似度和尾部相似度。然后，他决定找出使相似值总和最大的分割方法。

给你长度为N NN的整数序列A = ( A 1 , A 2 , … , A N ) A = (A_1, A_2, \ldots, A_N)A=(A1​,A2​,…,AN​)、B = ( B 1 , B 2 , … , B N ) B = (B_1, B_2, \ldots, B_N)B=(B1​,B2​,…,BN​)和C = ( C 1 , C 2 , … , C N ) C = (C_1, C_2, \ldots, C_N)C=(C1​,C2​,…,CN​)。

求满足1 ≤ x < y < N 1 \le x < y < N1≤x<y<N的一对整数( x , y ) (x, y)(x,y)，最大化∑ i = 1 x A i + ∑ i = x + 1 y B i + ∑ i = y + 1 N C i \displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_ii=1∑x​Ai​+i=x+1∑y​Bi​+i=y+1∑N​Ci​的值。

【输入】

输入内容由标准输入法提供，格式如下

N NN
A 1 A_1A1​A 2 A_2A2​… \ldots…A N A_NAN​
B 1 B_1B1​B 2 B_2B2​… \ldots…B N B_NBN​
C 1 C_1C1​C 2 C_2C2​… \ldots…C N C_NCN​

【输出】

输出答案。

【输入样例】

5 1 4 2 4 3 2 3 4 2 2 3 2 4 4 3

【输出样例】

16

【算法标签】

《洛谷 AT_abc438_d Tail of Snake》 #动态规划DP# #前缀和#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 定义int为long long，防止溢出constintN=300005;intn;// 天数inta[N],b[N],c[N];// 每天的三种选择intsa[N],sb[N],sc[N];// 前缀和数组inttmp[N];// 后缀最大值数组signedmain()// signed是int的别名，因为定义了#define int long long{// 输入天数cin>>n;// 输入a数组并计算前缀和safor(inti=1;i<=n;i++){cin>>a[i];sa[i]=sa[i-1]+a[i];// sa[i] = a[1]到a[i]的和}// 输入b数组并计算前缀和sbfor(inti=1;i<=n;i++){cin>>b[i];sb[i]=sb[i-1]+b[i];// sb[i] = b[1]到b[i]的和}// 输入c数组并计算前缀和scfor(inti=1;i<=n;i++){cin>>c[i];sc[i]=sc[i-1]+c[i];// sc[i] = c[1]到c[i]的和}// 预处理tmp数组：从后往前计算后缀最大值// tmp[i] = max_{j>=i} (sb[j] + (sc[n] - sc[j]))for(inti=n-1;i>1;i--){// 比较当前值sb[i] + 从i+1到n的c的和 与 后面的最大值tmp[i+1]tmp[i]=max(tmp[i+1],sb[i]+sc[n]-sc[i]);}// 输出调试信息（注释部分）// for (int i=1; i<=n; i++)// cout << tmp[i] << " ";// cout << endl;// for (int i=2; i<n; i++)// cout << tmp[i] << " ";// cout << endl;// 计算最终答案intans=-1;for(inti=1;i<n;i++){// 公式：sa[i] + tmp[i+1] - sb[i]ans=max(ans,sa[i]+tmp[i+1]-sb[i]);}cout<<ans<<endl;return0;}

【运行结果】

5 1 4 2 4 3 2 3 4 2 2 3 2 4 4 3 16