题解 P4870 【[BalticOI 2009 Day1]甲虫】

· · 题解

本题解重点讲解整体思路，细节见代码

确定做法

看到“数轴”和“最大价值”，自然而然地想到了区间DP，自己写了几个式子推了几种情况，发现不掉头或只掉一次头不一定最优，故排除贪心，大概确定做法为区间DP；观察数据范围，发现 n 是 O(n^3) 的范围，便想到可能要额外枚举某个条件后再跑一遍区间DP（伏笔）。

确定状态

先思考用 f 数组维护 l 到 r 区间可得的最大价值。本题中，每个水滴的价值（水分）随时都在变化，不同时间走到同一个点也可能会产生不同的价值，传统的区间DP状态 f[l][r] 无法同时维护时间和直接价值，因为时间的上界过大且无法离散化，所以也无法增加一维状态。

但是经过观察我们发现，一个区间的价值等于区间初始价值（水滴数乘以 m）减去流失的价值，很显然。但是重要的是对于每一个区间，剩下水滴的数目可以确定，而水分流失的总速度也就确定，所以可以用 f[l][r] 维护区间内已流失水分的最小值。

因为甲虫爬完区间后停在区间的哪一边（显然不可能是中间）不仅对本次的价值有影响，也影响下一次状态的转移，所以用 f[l][r] 和 f[r][l] 分别维护即可。

处理答案

维护了流失水分的最小值，输出答案时就要用总的水滴值减去这个最小值，产生了如下问题：

所以，我们考虑枚举这个“时间”，由于时间过大，我们用可以喝到的水滴数来限制时间，及枚举喝到的水滴数（呼应），对于每一个水滴数，单独跑一遍区间DP，答案为这些价值的最大值。

感性证明

从定义出发，甲虫喝到最多水的情况，必是已经喝过了所有的水滴或爬到下一个水滴时所有水滴已经蒸发完了。

如果枚举的水滴数大于了实际可以喝到的水滴数，则可以理解为甲虫在实际的最优情况下，又喝了一个价值为负的水滴，最后的价值必定小于最优价值，所以枚举一定能保证得到的最优价值是符合实际的。

Talk is cheap, show me the code

#include<bits/stdc++.h>
#define re register
using namespace std;

inline int read(){
    re int ret=0,f=1;
    re char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        ret=(ret<<1)+(ret<<3)+(c^48);
        c=getchar();
    } return ret*f;
}

int n,m,st,ans;
int loc[305];
int f[305][305];
//用f[i][j]和f[j][i]来代表停在哪一边 

bool IF; //判断是否有水滴在起始位置 

int main(){
    n=read(); m=read();
    for(re int i=1;i<=n;i++){
        loc[i]=read();
        if(!loc[i]) IF=1;
    } if(!IF) loc[++n]=0;
    //如没有水滴在起始位置，先添加一个，最后减去这个水滴的价值即可 
    sort(loc+1,loc+1+n);
    st=lower_bound(loc+1,loc+1+n,0)-loc;
    //0的位置 
    for(re int maxl=1;maxl<=n;maxl++){
        memset(f,63,sizeof(f)); f[st][st]=0;
        for(re int len=2;len<=maxl;len++){
            for(re int i=max(1,st-len+1),j;i<=st;i++){
                j=i+len-1; if(j>n) break;
                if(i<st){
                    f[i][j]=f[j][i+1]+(loc[i+1]-loc[i])*(maxl-j+i)+(loc[j]-loc[i])*(maxl-j+i-1);
                    f[j][i]=f[j][i+1]+(loc[i+1]-loc[i])*(maxl-j+i);
                }
                if(j>st){
                    f[i][j]=min(f[i][j],f[i][j-1]+(loc[j]-loc[j-1])*(maxl-j+i));
                    f[j][i]=min(f[j][i],f[i][j-1]+(loc[j]-loc[j-1])*(maxl-j+i)+(loc[j]-loc[i])*(maxl-j+i-1));
                }
                //状态转移要考虑从两边转移 
            }
        } //经典区间DP，不必多说 
        for(re int i=max(1,st-maxl+1),j,now;i<=st;i++){
            j=i+maxl-1; if(j>n) break;
            now=maxl*m-min(f[i][j],f[j][i])-(IF?0:m);
            ans=max(ans,now);
        }
    }
    printf("%d",ans);
    return 0;
}