题目大意

一个数轴上有 $n$ 滴水，每滴水最开始有 $m$ 的大小，每个单位时间内，所有水减小 $1$，你也可以移动一个单位长度，问最多能喝道多少水。

题目分析

与 P2466 [SDOI2008] Sue 的小球 有点像。（双倍经验）

在数轴上左右移动收集某些东西，很明显的区间 DP 特征。

常规状态 $f_{l, r, 0/1}$，表示收集完 $l\sim r$，最高分数，但是在收集一个水滴的时候，之前已经过去多长时间也会对这个点的贡献（即剩余水的大小）有影响，所以我们考虑如何边 dp，边算影响。由于 $v$ 不会变，可以一边 dp 一边将这一步用时对于还未收集的水滴的影响算上，直接加答案里。

转移方程为：

$$f_{l, r, 0} = \max\begin{cases}f_{l+1, r, 0} + (x_{l+1} - x_{l}) \times (n - r + l) + m \\ f_{l+1, r, 1} + (x_{r} - x_{l}) \times (n - r + l) + m \end{cases}$$

到这里就是上面那道题的大体思路了，但是这道题我们会发现有可能我们只选一部分是最优解，但是上面的转移我们已经预支了我们不取的那些水滴会减少的值。

但是我们发现上述算法是 $\mathcal O(n^2)$ 的，而这道题的数据范围很明显支持 $\mathcal O(n^3)$ 算法，于是我们不妨再枚举一下最终我们会选几个水滴，然后做 $n$ 次上述 DP。特别的，这次我们需要保证我们枚举的 $l, r$ 之差在限制范围内。

转移方程与上面差不多就不粘了。

code

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long

using namespace std;

const int N = 1e3 + 5, INF = 2e18;
int n, m, st, f[N][N][2], x[N], ans = 0;

signed main()
{
    scanf("%lld %lld", &n, &m);
    for(int i = 1;i <= n;i++)  scanf("%lld", &x[i]);
    x[++n] = 0;
    sort(x + 1, x + n + 1);
    for(int i = 1;i <= n;i++)
    {
        if(x[i] == 0)
            st = i;
    }
    for(int k = 1;k <= n;k++)
    {
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                f[i][j][1] = f[i][j][0] = -INF;
        f[st][st][1] = f[st][st][0] = 0;
        for(int l = st;l >= 1;l--)
        {
            for(int r = st;r <= n && r - l < k;r++)
            {
                if(l == st && r == st)  continue;
                f[l][r][0] = max(f[l][r][0], f[l+1][r][0] - (x[l+1] - x[l]) * (k - r + l) + m);
                f[l][r][0] = max(f[l][r][0], f[l+1][r][1] - (x[r] - x[l]) * (k - r + l) + m);

                f[l][r][1] = max(f[l][r][1], f[l][r-1][0] - (x[r] - x[l]) * (k - r + l) + m);
                f[l][r][1] = max(f[l][r][1], f[l][r-1][1] - (x[r] - x[r-1]) * (k - r + l) + m);
                ans = max(ans, f[l][r][0]);
                ans = max(ans, f[l][r][1]);
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}