P4870 [BalticOI 2009 Day1] 甲虫题解

all_for_god · 2025-01-20 20:34:51 · 题解

P4870 [BalticOI 2009 Day1] 甲虫

首先数据范围很小，而每个水珠的贡献一直在变化。

由于所有水珠的初始水量都相同，因此如果我们知道了经过的时间，那我们就可以统计每个水珠的贡献。

但是时间范围太大了，不好直接去放在状态里。那如何抛弃掉巨大的 m 与 x_i 让时间复杂度与 n 挂钩呢？

于是我们倒过来想，由于时间复杂度可以支持到 n^3，因此我们直接去枚举到底要吃多少个水珠，去计算总共亏损了多少水量。

然后就是区间DP的套路了，设 f_{l,r,0/1} 表示吃完了 l 到 r 之间的水珠之后站在左或者右端点的亏损的最小值。

而状态转移就如下（这个应该得会吧）：

f[l][r][0]=min({f[l][r][0],f[l+1][r][0]+(num-(r-l))*(loc[l+1]-loc[l]),f[l+1][r][1]+(num-(r-l))*(loc[r]-loc[l])});
f[l][r][1]=min({f[l][r][1],f[l][r-1][1]+(num-(r-l))*(loc[r]-loc[r-1]),f[l][r-1][0]+(num-(r-l))*(loc[r]-loc[l])});

表示的就是站在左边或者站在右边从左边或者右边走过来需要亏的水量。num 指枚举的要吃水珠的数量。

由于当前这个暂时还没有吃（中间的路还要赶），因此还剩下 num-(r-l+1)+1 个水珠还没有吃，也就是还在晒着亏水量。

而答案就是

m*(r-l)-min(f[l][r][0],f[l][r][1])

取max。

注意这里假设水珠水量可以被晒成负数。能够这样处理的原因是如果水被晒成负数，那一定不优，因此不会选。

关于为何不是 m*(r-l+1) 的问题，应该不是因为所谓的 “因为还没喝掉要喝的水，所以减一”，而是因为在开头：

for(int i=1;i<=n;i++) cin>>loc[i],z=(loc[i]==0)||z;
if(!z) loc[++n]=0;

这是避免没有水滴在 0 处不好 DP 的问题。因此我们直接强制在 0 处加上一个水滴，然后这里就需要考虑到不能多算一个水滴的答案，就要减一。

但是如果本来有水滴在 0 处，就要把多减的加回去：

cout<<ans+z*m<<'\n';

因此如果你愿意也可以写成这样：

m*(r-l+1)-min(f[l][r][0],f[l][r][1])

cout<<(ans==0?0:(ans-(z^1)*m))<<'\n';

但很可惜本题并没有 0 处有水滴的情况，建议加一下 hack。时间复杂度 O(n^3)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=605;
const int inf=1e18;
int n,m,loc[N],ans=0,f[N][N][2],pos;bool z=0;
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>loc[i],z=(loc[i]==0);
    if(!z) loc[++n]=0;
    sort(loc+1,loc+n+1);pos=lower_bound(loc+1,loc+n+1,0)-loc;
    for(int num=2;num<=n;num++) 
    {
        memset(f,0x3f,sizeof(f));
        f[pos][pos][0]=f[pos][pos][1]=0;
        for(int len=2;len<=num;len++) 
        for(int l=1;l+len-1<=n;l++)
        {
            int r=l+len-1;
            f[l][r][0]=min({f[l][r][0],f[l+1][r][0]+(num-(r-l))*(loc[l+1]-loc[l]),f[l+1][r][1]+(num-(r-l))*(loc[r]-loc[l])});
            f[l][r][1]=min({f[l][r][1],f[l][r-1][1]+(num-(r-l))*(loc[r]-loc[r-1]),f[l][r-1][0]+(num-(r-l))*(loc[r]-loc[l])});
            ans=max({ans,m*(r-l)-min(f[l][r][0],f[l][r][1])});
        }
    }
    cout<<ans+z*m<<'\n';return 0;
}

然后最近写了几道单调性，想可不可以优化，发现还真行。

由于少喝水滴一定会劣，如果假定水滴可能减少为负数（就是本题的处理方法），再喝已经为负数的水滴也一定劣。那么答案就一定会形成一个在吃的水滴数为x轴，最优答案为y轴的坐标系里的严格的上凸壳。

感觉已经够清楚了。然后就是找上凸壳的顶点，三分。时间复杂度 O(n^2\log n) ~~然后就被 O(n^3) 吊打~~

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=605;
const int inf=1e18;
int n,m,loc[N],ans=0,f[N][N][2],pos;bool z=0;
int solve(int num)
{
    int res=0;
    memset(f,0x3f,sizeof(f));
    f[pos][pos][0]=f[pos][pos][1]=0;
    for(int len=2;len<=num;len++) 
    for(int l=1;l+len-1<=n;l++)
    {
        int r=l+len-1;
        f[l][r][0]=min({f[l][r][0],f[l+1][r][0]+(num-(r-l))*(loc[l+1]-loc[l]),f[l+1][r][1]+(num-(r-l))*(loc[r]-loc[l])});
        f[l][r][1]=min({f[l][r][1],f[l][r-1][1]+(num-(r-l))*(loc[r]-loc[r-1]),f[l][r-1][0]+(num-(r-l))*(loc[r]-loc[l])});
        res=max({res,m*(r-l)-min(f[l][r][0],f[l][r][1])});
    }ans=max(ans,res);
    return res;
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>loc[i],z=(loc[i]==0)||z;
    if(!z) loc[++n]=0;
    sort(loc+1,loc+n+1);pos=lower_bound(loc+1,loc+n+1,0)-loc;
    int l=1,r=n;
    while(l<r-1)
    {
        int mid=(l+r)>>1,mmid=(mid+r)>>1,resm=solve(mid),resmm=solve(mmid);
        if(resm>resmm) r=mmid;else l=mid;
    }
    ans=max({ans,solve(l),solve(r)});
    cout<<ans+z*m<<'\n';return 0;
}

蒟蒻的第一篇题解，点个赞呗：）

P4870 [BalticOI 2009 Day1] 甲虫 题解

P4870 [BalticOI 2009 Day1] 甲虫

P4870 [BalticOI 2009 Day1] 甲虫题解