P4870 [BalticOI 2009 Day1]甲虫

题意：

有一只甲虫处于一根水平的树枝。因为他沉迷数学无法自拔，所以他觉得很像是在 \(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:也就多转了个弯，难度就上紫了（