【学而思编程】P7813 题解

题目
https://www.luogu.com.cn/problem/P7813

不难发现第 n 行有 n 个数, 第 n - 1 行有 n - 1 个数, 这两行共有 2n - 1 个数
(会有人发现不了吗(
我们看数据范围

也就是说

也就是说, 最多只会取相当于最后两行数量的数
因为越向下的数字越大, 我们只需要考虑最后两行就行了
考虑贪心, 从第 n 行第 n 个数, 也就是第 n 行最大的数开始
随后选择第 n - 1 行有 n - 1 个数, 也就是第 n - 1 行最大的数
然后再回到第 n 行, 选择第 n - 1 个数
也就是说, 我们要在第 n 行和第 n - 1 行反复横跳, 每次都选择这行最大的数, 这样就能使和最大化

## 优化
我们以样例一举例:

我们选择了13 -> 9 -> 14 -> 10 -> 15 这条路径
我们可以将其视作在第 5 行选了三个最大的, 在第 4 行选了两个最大的, 完成了选择 5 个数字的目标
我们推广一下, 任何这种问题都可以视作在第 N 行选 x 个最大的, 在第 N - 1 行选 y 个最大的
当选择个数为偶数时, 显然

当选择个数为奇数时, 因为第 N 行的数字总比第 N - 1 行的数字大, 所以

第 n 行第 n 个数的值为

显然第 n 行第个数的值为

第 n 行取 x 个最大的数, 它们的和为

我们只需要分别将第 n 行与第 n - 1 行的情况代入求和就行了
这里注意 n ^ 2 最大能达到 10 ^ 18 , 因此需要使用 long long存储, 并且运算过程中还要取模
这也是最后一步没有完全乘开的原因, a * n ^ 2 会爆 long long

代码

在我的博客上看这篇题解：https://blog.atomalpaca.xyz/2021/P7813-%E8%B0%9C-%E9%A2%98%E8%A7%A3/