一、题目
二、解法
一看 n ≤ 300 n\leq 300 n≤300 就知道是区间 d p dp dp 的题，只不过露水有点难以计算。
区间 d p dp dp 应该是 O ( n 2 ) O(n^2) O(n2) 的，所以他多留了 O ( n ) O(n) O(n) 给我们解决这个问题。可以先枚举最后要喝多少露水，那么 d p dp dp 的时候就可以算经过边的贡献，也就是后面的还未经过的露水会因为经过这一条边而蒸发（其实就是费用提前计算）
设 d p [ i ] [ j ] [ 0 / 1 ] dp[i][j][0/1] dp[i][j][0/1] 为访问完 [ i , j ] [i,j] [i,j] 最后停在左端点 / / /右端点的最大露水数，这样已经和了的露水和还没喝的露水我们都知道了。转移分为两种，第一种是 [ i , j ] [i,j] [i,j] 和 [ i + 1 , j ] , [ i , j − 1 ] [i+1,j],[i,j-1] [i+1,j],[i,j−1] 之间的转移 ，第二种是左右端点之间的转移（可以从区间的一段到其另一端）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 305;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,o,ans,a[M],dp[M][M][2];
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
a[i]=read();
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
if(a[i]<0) o=i;
for(int k=1;k<=n;k++)
{
memset(dp,-0x3f,sizeof dp);
dp[o][o][0]=dp[o][o][1]=m+a[o]*k;
dp[o+1][o+1][0]=dp[o+1][o+1][1]=m-a[o+1]*k;
for(int l=1;l<k;l++)
for(int i=1;i+l<=n;i++)
{
int j=i+l;
dp[i][j][0]=max(dp[i][j][0],dp[i+1][j][0]+m-(k-l)*(a[i+1]-a[i]));
dp[i][j][1]=max(dp[i][j][1],dp[i][j-1][1]+m-(k-l)*(a[j]-a[j-1]));
dp[i][j][0]=max(dp[i][j][0],dp[i][j][1]-(k-l-1)*(a[j]-a[i]));
dp[i][j][1]=max(dp[i][j][1],dp[i][j][0]-(k-l-1)*(a[j]-a[i]));
}
for(int i=1;i+k-1<=n;i++)
ans=max(ans,max(dp[i][i+k-1][0],dp[i][i+k-1][1]));
}
printf("%d\n",ans);
}