题解 P3580 【[POI2014]ZAL-Freight】

· · 题解

个人DP时想傻掉了，但是最终还是用奇妙的方式实现了这个傻掉的做法，因此发一篇题解。

首先，状态非常好设，f_i 表示 i 以及之前的所有车次全都跑回去再跑回来的最小时间即可。

本质上是一个优化DP的过程。

我们考虑最暴力的 O(n^2) DP，即从一个 f_i 出发，递增地枚举 j，并求出此时 i\rightarrow j 的最小时间（因为要满足“相邻差大于等于 1”的限制），然后转移即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[1001000];
ll f[1001000]; 
int main(){
    scanf("%d%d",&n,&m),memset(f,0x3f,sizeof(f)),a[0]=-1;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    f[0]=0;
    for(int i=0;i<n;i++){
        ll now=f[i]-1;
        for(int j=i+1;j<=n;j++){
            now++,now=max(now,1ll*a[j]);
            f[j]=min(f[j],now+2*m+(j-i-1));
        }
    }
    printf("%lld\n",f[n]);
    return 0;
}

但是，这个DP非常令人不爽，因为我们没有办法通过什么式子直接表示出 i\rightarrow j 的最小代价。

这时就要祭出一个不怎么常见的应用于题目中所述的递增序列的小trick了：

如果一个序列 a 递增，那么 a_i-i 不降。

我们考虑将其应用于上述DP：

序列 \{f_i-1,a_{i+1},a_{i+2},\dots,a_j\} 递增。

减一下就发现，序列 \{f_i-i-1,a_{i+1}-(i+1),\dots,a_j-j\} 不降。

于是我们只需要先把整个序列转成上述 a_i-i 的形式，然后最小代价就直接取区间 \max 就能得出，最后再把它恢复成 a_i 的形式即可。

于是我们现在便可以有一个DP的式子了：

f_j=\min\limits_{i<j}\Bigg\{\max\Big\{f_i-i-1,\max\{a_{i+1},\dots,a_j\}\Big\}+2(m+j)-i+1\Bigg\}

虽然还是 O(n^2) 的DP，但是写出式子就是一大进步。

此部分代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[1001000];
ll f[1001000]; 
int main(){
    scanf("%d%d",&n,&m),memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]-=i;
    f[0]=0;
    for(int i=0;i<n;i++){
        ll now=f[i]-i-1;
//      printf("%d\n",now);
        for(int j=i+1;j<=n;j++){
            now=max(now,1ll*a[j]);
//          printf("%d->%d:%d\n",i,j,now);
            f[j]=min(f[j],now+j+2*m+(j-i-1));
        }
    }
//  for(int i=0;i<=n;i++)printf("%lld ",f[i]);puts("");
    printf("%lld\n",f[n]);
    return 0;
}

现在考虑上奇怪的东西来维护了。

我们翻出式子

f_j=\min\limits_{i<j}\Bigg\{\max\Big\{f_i-i-1,\max\{a_{i+1},\dots,a_j\}\Big\}+2(m+j)-i+1\Bigg\}

提取一些东西出来

f_j=2(m+j)+1+\min\limits_{i<j}\Bigg\{\max\Big\{f_i-i-1,\max\{a_{i+1},\dots,a_j\}\Big\}-i\Bigg\}

然后里面的东西，我们可以分情况讨论。

  1. f_i-i-1\geq\max\{a_{i+1},\dots,a_j\}

首先，f_i 肯定是单调递增的，因为多一辆车你统一回来时就要多等一秒，则 f_i 至少比 f_{i-1} 大一。于是 f_i-i-1 便是单调不降的。

所以我们便可以用two-pointers维护第一个不满足上述条件的 j。于是，对于所有 k\in(i,j)，都有 f_i-i-1-i\rightarrow f_k。

考虑随着 i 上升， j 也是单调不降的，故此部分可以上单调队列维护。

  1. f_i-i-1<\max\{a_{i+1},\dots,a_j\}

此处有 \max\{a_{i+1},\dots,a_k\}-i\rightarrow f_k。根据我们上述的总结，此部分应该作用于一个后缀 [j,n]。

考虑位置 j。显然，此处必然有 \max\{a_{i+1},\dots,a_j\}=a_j，不然 j 不可能是第一个满足上述条件的位置。故我们可以将上述条件转为

\max\{a_j,\dots,a_k\}-i\rightarrow f_k

特别地，在 j 处，上式等价于

a_j-i\rightarrow f_j

考虑在 j 处开一个桶 g 记录所有可以转移的最大后缀是 [j,n] 的 i 中，最大的一个。则必有桶中的值（假如桶中有值的话）随着 j 的增大不降。

我们考虑对于位置 j，它还从前面继承过来一个 \max\{a_p,\dots,a_j\}-q\rightarrow f_j。则根据我们之前的分析，假如桶中有值，必有 \max\{a_p,\dots,a_j\}\geq a_j 且 q\leq g_j。即，\max\{a_p,\dots,a_j\}-q\geq a_j-g_j。

故我们可以无条件把前面继承过来的东西换成位置 j 桶中的东西。当然，如果 j 中桶里是空的，当然就换不了了。

则时间复杂度 O(n)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[1001000],g[1001000],nowa,nowb=-1;
ll f[1001000];
deque<pair<ll,int> >q;
int main(){
    scanf("%d%d",&n,&m),memset(f,0x3f,sizeof(f)),memset(g,-1,sizeof(g));
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]-=i;
//  for(int i=1;i<=n;i++)printf("%d ",a[i]);puts("");
    f[0]=-2*m+1;
    for(int i=0,j=1;i<=n;i++){
        while(!q.empty()&&q.front().second<=i)q.pop_front();
        if(!q.empty())f[i]=min(f[i],q.front().first);

        if(g[i]!=-1)nowa=a[i],nowb=g[i];
        nowa=max(nowa,a[i]);
        if(nowb!=-1)f[i]=min(f[i],1ll*nowa-nowb);

        f[i]+=2*(i+m)-1;
        ll now=f[i]-i-1;
        for(j=max(i+1,j);j<=n&&now>=a[j];j++);
//      printf("%d:%d\n",now,j);
        while(!q.empty()&&q.back().first>=now-i)q.pop_back();
        q.push_back(make_pair(now-i,j));
        g[j]=max(g[j],i);
    }
//  for(int i=0;i<=n;i++)printf("%lld ",f[i]);puts("");
    printf("%lld\n",f[n]);
    return 0;
}