除了 C 题都是普及组难度，可是他偏偏不把 C 放 E, 而放在了 C, 所以我就一直困在 C 了……最后时刻想起了 SOP, 于是去写了 D。

C

数轴上 $n$ 个点，上面有一个数，每过 $1$ 秒每个正数会减少 $1$, 问从 $0$ 开始以 $1$ 格每秒的速度去收集最多能收集到多少。

开始的时候当然是想到贪心的，但是比赛的时候找到了几个不同贪心的反例，于是就放弃了贪心的想法，开始转战 dp。

开始联想到了那场 ABC，于是很快就发现了一定是停在左边或者右边的性质，并确定了区间 dp。然后开始考虑转移了。同样参照那场 abc 决定在中间枚举一个断开的断点，然后发现这是不可行的，因为 AT 的那道是决定了出场的顺序，然后决策拿多少，和这个的条件和求法都不一样。

而且本题中一段在中途折返到另一段似乎没有办法直接跨区域转移，所以得用另外一种区间 dp 的转移了，就是只把头或尾的去掉，然后转移。

这样就可以得出一个大概的方程， $f[i][j][0] = \min\{f[i+1][j][0] + (a[i+1]-a[i]) \times?, f[i+1][j][1] + (a[j]-a[i]) \times ?\}$

那么这个问号是什么东西呢？就是要对后续产生的贡献，手动模拟一下容易发现，应该是所有没有被去掉的在这一段中被减去的，可是我们并不知道一共有几个，所以还得枚举一下，设当前取了 $p$ 个，那么就是要乘上 $p - [j-(i+1) + 1]$，在枚举状态的时候我们会用到 $len$, 所以直接写作 $p-len+1$ 就可以了。

另一个的转移同理，最后统计答案就是再枚举一次起点统计 $(p-1) \times m$ （减一是因为多补充了一个 $0$）, 减去 $f[i][i+p-1][0/1]$ 中的最小值就可以了。

代码。

#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 305; 
int n, m, a[N], s, f[N][N][2], ans;
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	a[++n] = 0;
	std::sort(a+1, a+1+n);
	s = std::lower_bound(a+1, a+1+n, 0) - a;
	for(int p = 1; p <= n; p++) {
		memset(f, 0x3f, sizeof f);
		f[s][s][0] = f[s][s][1] = 0;
		for(int len = 2; len <= p; len++)
			for(int i = 1; i + len - 1 <= n; i++) {
				int j = i + len - 1;
				f[i][j][0] = std::min(f[i+1][j][0] + (a[i+1]-a[i]) * (p-len+1), 
									  f[i+1][j][1] + (a[j] - a[i]) * (p-len+1));
				f[i][j][1] = std::min(f[i][j-1][1] + (a[j]-a[j-1]) * (p-len+1),
									  f[i][j-1][0] + (a[j] - a[i]) * (p-len+1));
			}
		for(int i = 1; i <= n-p+1; i++)
			ans = std::max(ans, (p-1) * m - std::min(f[i][i+p-1][0], f[i][i+p-1][1]));
	}
	printf("%d", ans);
	return 0;
}

现在完成了这题，再来反思一下考场上想的 dp 为什么不可以。其实关键是在于对后面的贡献没有得到很好的处理。用原来的转移其实也可以用类似 $(a[j]-a[i]) \times (p-len+1)$ 的方式去处理贡献，不过由于中间会跨过很多 $a$, 所以不能一下子处理出来，还需要一层循环来解决，不过其本质上是和这种只跨过一个的转移是等价的。

赛场上想不出转移思路就又到奇奇怪怪的方向上去了，搞了一些没有本质上不同的变换，比如把它等价成一个矩阵上的操作，这样的思路看上去不一样，而实际上没有减少任何的重复和不必要，应该及时悬崖勒马。