解析
考试\(T3\)，正解不会，暴力打挂，惨兮兮。
类似于费用提前计算的题目：SDOI2008 Sue的小球（好像就是因为这道题才去学这个的
定义\(f[0/1][i][j]\)表示吃掉\([i,j]\)露水并且停留在最左端/最右端的最大水分。
转移：\(f[0][i][j]=min(f[0][i+1][j]+(x[i+1]-x[i])*(i+n-j),f[1][i+1][j]+(x[j]-x[i])*(i+n-j))\)
\(f[1][i][j]=min(f[1][i][j-1]+(x[j]-x[j-1])*(i-1+n-(j-1)),f[0][i][j-1]+(x[j]-x[i])*(i-1+n-(j-1)))\)
但是这道题有个问题就是，它符合物理常识，水分蒸发了就没有了，而不会变成负数，换句话说，就是没有上道题的\(Sue\)要求你捞全部的彩球，人家甲虫要活命的，只要求水分最大。
如果挨个计算每个水滴是不是负数，那么复杂度无疑会很大（而且优化也搞没了好嘛
所以可以枚举一下吃掉露水的数量，每个数量取最大值。可以发现这样做的话，负数的情况一定不优，所以可以规避掉。
►Code View
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 305
#define INF 0x3f3f3f3f
#define LL long long
int rd()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f*x;
}
int n,m;
int x[N];
LL f[2][N][N],ans;
int Abs(int x)
{
if(x>=0) return x;
return -x;
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<=n;i++)
x[i]=rd();
x[++n]=0;
sort(x+1,x+n+1);
int st;
for(int i=1;i<=n;i++)
if(x[i]==0)
{
st=i;
break;
}
for(int p=1;p<=n;p++)
{
memset(f,INF,sizeof(f));
f[0][st][st]=f[1][st][st]=0;
for(int len=1;len<=p;len++)
for(int i=1;i+len<=n;i++)
{
int j=i+len;
f[0][i][j]=min(f[0][i+1][j]+Abs(x[i+1]-x[i])*(i+p-j),f[1][i+1][j]+Abs(x[j]-x[i])*(i+p-j));
f[1][i][j]=min(f[1][i][j-1]+Abs(x[j-1]-x[j])*(i-1+p-(j-1)),f[0][i][j-1]+Abs(x[i]-x[j])*(i-1+p-(j-1)));
}
for(int i=1;i+p-1<=n;i++)
ans=max(ans,1ll*m*(p-1)-min(f[0][i][i+p-1],f[1][i][i+p-1]));
}
printf("%lld\n",ans);
return 0;
}