题意：
有一只甲虫处于一根水平的树枝。因为他沉迷数学无法自拔，所以他觉得很像是在 \(x\) 轴上。
在同一根树枝上，还有 \(n\) 滴露水。每滴露水占用 \(m\) 个单位的水分。相对于甲虫的位置，他们的坐标分别是 \(x_1,x_2,\dots,x_n\)。
显然，这一天将会骄阳似火。每过一个时间单位，就会有一个单位的水分从每一滴露水流失。这只甲虫受尽了烈阳的折磨，以至于每当它碰到一滴露水都能瞬间喝完。在每个时间单位中它能移动一个单位的距离。
所以你要写一个程序，根据露水的坐标，计算出甲虫最多能喝到的水。
分析：
与关路灯那一道题相比，这个题恶心的点就在于水是会减少的，但减少到0时就不减少了。类比过去就相当于某个灯的功率减少到0就不变了，因此不能单纯地dp最少的浪费量。
那么，假如抛弃水滴数量减少到0就不变了这个条件，直接嗯dp，怎么才能消除影响呢？
考虑一段水的区间，长度为 \(c\)，那么一共就有 \(m * c\) 这么多滴水。总数 - 浪费量就是你所能获得的水的数量。尽管按这个思路dp出的浪费量可能会过大以至于能获得的水的数量为负数，不过因为是取的max，也就无伤大雅。
总的思路如下：
- 按 P1220 dp出每个区间的最小浪费数。
- 枚举每个区间，算出最大得到水的数量作为ans
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 300;
int st,n,m,x[MAXN + 5],dp[MAXN + 5][MAXN + 5][2];
bool flag;
signed main(){
scanf("%lld%lld",&n,&m);
for(int i = 1; i <= n; i++){
scanf("%lld",&x[i]);
if(!x[i]){
flag = 1;
}
}
if(!flag)++n;
sort(x + 1,x + 1 + n);
for(int i = 1; i <= n; i++){
if(x[i] == 0){
st = i;
break;
}
}
int ans = 0;
for(int c = 1; c <= n; c++){
memset(dp,0x3f,sizeof dp);
dp[st][st][0] = dp[st][st][1] = 0;
for(int len = 2; len <= c; len++){
for(int l = 1; l + len - 1 <= n; l++){
int r = l + len - 1;
dp[l][r][1] = min(dp[l][r - 1][1] + (x[r] - x[r - 1]) * (c - len + 1),dp[l][r - 1][0] + (x[r] - x[l]) * (c - len + 1));
dp[l][r][0] = min(dp[l + 1][r][0] + (x[l + 1] - x[l]) * (c - len + 1),dp[l + 1][r][1] + (x[r] - x[l]) * (c - len + 1));
}
}
for(int i = 1; i + c - 1 <= n; i++){
ans = max(ans,m * c - dp[i][i + c - 1][0]);
ans = max(ans,m * c - dp[i][i + c - 1][1]);
}
}
if(!flag)ans -= m;
cout << ans;
}
ps:也就多转了个弯，难度就上紫了（