AT_abc369 补题报告【G】

zhangjinxuan

题目：https://atcoder.jp/contests/abc369/tasks.
问题 C
数一个数列有多少个区间是等差数列
先做一次差分，那么一个区间当且仅当是等差数列，就是这个差分数组上的数字全部相同，然后做完了。
问题 D
一个序列的权值为其偶数位置和的两倍与奇数位置的和，求 A 权值最大的子序列
偶数奇数显然可以维护，因此动态规划即可。
问题 E
一张图，有 $Q$ 次询问，每一次询问给定不超过 $5$ 个边的边的编号，要求一定经过这些边，求 $1\to N$ 的最小路径长度
由于 $N\le400$，所以先做一次 Floyd 来求出所有的最短路，然后枚举这 $5$ 条边的排列情况，包括方向，然后就做完了。
问题 F
一个 $H\times W$ 的网格图，$N$ 个格点有硬币，求从左上向右或向下走到右下角可以获得的最多硬币数量。
如果吧硬币的 $(x,y)$ 坐标按照从小到大的顺序排序，那么就是一个简单的二维偏序问题，一个硬币 $(a,b)$ 能够接上 $(c,d)$，就是 $a\le c \land b\le d$，树套树即可。