NOIP2018PJ T3 摆渡车

傷城~ 2021-12-11 23:32 148阅读 0赞

[题目链接][Link 1]

### 题意： ###

时间轴上分布着$n$位乘客，$i$号乘客的位置为$t\_i$，用互相距离不小于$m$的车次将时间轴分为若干部分并管辖上一个区间，求最小费用和。每个车次的费用来自：管辖区间内乘客与区间左端点的距离之和。

## ##

### 程序1（30pt）： ###

考虑DP。

设在$i$时间的车次及之前所有费用之和的最小值为$f\_i$，则

①若是第一趟车，则

$$f\_i=\\sum\\limits\_\{1\\leq j\\leq i\}(\\, i-j\\,)$$

②若非第一趟车，则

$$f\_i=\\mathop\{min\}\\limits\_\{1\\leq j\\leq i-m\}\\\{\\, f\_j+\\;\\sum\\limits\_\{j+1\\leq k\\leq i\}(\\, i-k\\,) \\;\\\}$$

考虑答案在哪里，可以发现要接走最后一位乘客，设其等车时间为$T$,则最后一趟车发车时间必在$\[\\,T,T+m\\,)$中。

DP做完了。然而时间复杂度为$O(T^3)$，只有$30$分。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #define IL inline
    using namespace std;
    const int inf=1<<30;
    const int N=500;
    const int M=100;
    const int T=10000;
    
        int n,m;
        int maxt;
        int cnt[T+M+3];
        int f[T+M+3];
    
    int main(){
        scanf("%d%d",&n,&m);
        maxt=-inf;
        memset(cnt,0,sizeof cnt);
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            cnt[x]++;
            maxt=max(maxt,x);
            
        }
        
        for(int i=1;i<maxt+m;i++){
            f[i]=0;
            for(int j=1;j<=i;j++)
                f[i]+=cnt[j]*(i-j);
            
            for(int j=1;j<=i-m;j++){
                int tot=1;
                for(int k=j+1;k<=i;k++)
                    tot+=cnt[k]*(i-k);
                
                f[i]=min(f[i],f[j]+tot);
                
            }
            
        }
        
        for(int i=1;i<m;i++)
            f[maxt]=min(f[maxt],f[maxt+i]);
        
        printf("%d",f[maxt]);
        
        return 0;
        
    }

### 程序2（50pt）： ###

发现DP转移里的计算有很多重复部分，考虑使用**前缀和优化**。

对转移和式进行变形：

$$\\sum\\limits\_\{j+1\\leq k\\leq i\}(\\, i-k \\,)=\\sum\\limits\_ki-\\sum\\limits\_kk$$

设$cnt\_i$为乘客计数的前缀和，$sum\_i$为乘客时间的前缀和，则原式

$$=(\\, cnt\_i-cnt\_j \\,)\\times i\\;-\\;(\\, sum\_i-sum\_j \\,)$$

于是我们就可以$O(1)$转移了，整体时间复杂度下降到$O(t^2)$，可以得到$50$分。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #define IL inline
    using namespace std;
    const int inf=1<<30;
    const int N=500;
    const int M=100;
    const int T=4000000;
    
        int n,m;
        int maxt;
        int sum[T+M+3];
        int cnt[T+M+3];
        int f[T+M+3];
    
    int main(){
        scanf("%d%d",&n,&m);
        maxt=-inf;
        memset(cnt,0,sizeof cnt);
        memset(sum,0,sizeof sum);
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            maxt=max(maxt,x);
            cnt[x]++;
            sum[x]+=x;
            
        }
        
        for(int i=1;i<maxt+m;i++){
            cnt[i]+=cnt[i-1];
            sum[i]+=sum[i-1];
            
        }
        
        for(int i=1;i<maxt+m;i++){
            f[i]=cnt[i]*i-sum[i];
            for(int j=1;j<=i-m;j++)
                f[i]=min(f[i]
                        ,f[j]+(cnt[i]-cnt[j])*i
                             -(sum[i]-sum[j]));
            
        }
        
        for(int i=1;i<m;i++)
            f[maxt]=min(f[maxt],f[maxt+i]);
        
        printf("%d",f[maxt]);
        
        return 0;
        
    }

### 程序3（70pt）： ###

发现DP时每次都从$0$开始转移，显然是多余的，需要**剪去无用转移**。思考一下，发现如果我们切出了一个长度超过$2m$的段，我们可以至少再分一次，得到一个不劣的答案。

于是乎

$$f\_i=\\mathop\{min\}\\limits\_\{i-2m< j\\leq i-m\}\\\{\\, f\_j+\\;(\\, cnt\_i-cnt\_j \\,)\\times i\\;-\\;(\\, sum\_i-sum\_j \\,) \\;\\\}$$

这次的时间复杂度是$O(tm)$的，可以得到$70$分。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #define IL inline
    using namespace std;
    const int inf=1<<30;
    const int N=500;
    const int M=100;
    const int T=4000000;
    
        int n,m;
        int maxt;
        int sum[T+M+3];
        int cnt[T+M+3];
        int f[T+M+3];
    
    int main(){
        scanf("%d%d",&n,&m);
        maxt=-inf;
        memset(cnt,0,sizeof cnt);
        memset(sum,0,sizeof sum);
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            maxt=max(maxt,x);
            cnt[x]++;
            sum[x]+=x;
            
        }
        
        for(int i=1;i<maxt+m;i++){
            cnt[i]+=cnt[i-1];
            sum[i]+=sum[i-1];
            
        }
        
        for(int i=1;i<maxt+m;i++){
            f[i]=cnt[i]*i-sum[i];
            for(int j=max(i-2*m,1);j<=i-m;j++)
                f[i]=min(f[i]
                        ,f[j]+(cnt[i]-cnt[j])*i
                             -(sum[i]-sum[j]));
            
        }
        
        for(int i=1;i<m;i++)
            f[maxt]=min(f[maxt],f[maxt+i]);
        
        printf("%d",f[maxt]);
        
        return 0;
        
    }

### 程序4（100pt）： ###

看起来转移已经很简洁了，但我们仍然没有得到满分。思考一下，发现我们对于每个时间点（$0\\sim t$）都尝试进行转移，但真正有贡献的点（规模为$O(nm)$）实际上却少很多。

考虑**剪去无用状态**，发现一个长度不小于$m$的时间段不会产生任何贡献，即：若

$$cnt\_i\\,=\\,cnt\_\{i-m\}$$

则一定有

$$f\_i\\,=\\,f\_\{i-m\}$$

考虑时间复杂度，因为只在有贡献的地方转移，所以是$O(\\,t\\,+\\,nm^2\\,)$，可以得到满分。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #define IL inline
    using namespace std;
    const int inf=1<<30;
    const int N=500;
    const int M=100;
    const int T=4000000;
    
        int n,m;
        int maxt;
        int sum[T+M+3];
        int cnt[T+M+3];
        int f[T+M+3];
    
    int main(){
        scanf("%d%d",&n,&m);
        maxt=-inf;
        memset(cnt,0,sizeof cnt);
        memset(sum,0,sizeof sum);
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            maxt=max(maxt,x);
            cnt[x]++;
            sum[x]+=x;
            
        }
        
        for(int i=1;i<maxt+m;i++){
            cnt[i]+=cnt[i-1];
            sum[i]+=sum[i-1];
            
        }
        
        for(int i=1;i<maxt+m;i++){
            if(i>=m)
            if(cnt[i]==cnt[i-m]){
                f[i]=f[i-m];
                continue;
                
            }
            
            f[i]=cnt[i]*i-sum[i];
            for(int j=max(i-2*m,1);j<=i-m;j++)
                f[i]=min(f[i]
                        ,f[j]+(cnt[i]-cnt[j])*i
                             -(sum[i]-sum[j]));
            
        }
        
        for(int i=1;i<m;i++)
            f[maxt]=min(f[maxt],f[maxt+i]);
        
        printf("%d",f[maxt]);
        
        return 0;
        
    }

### 小结： ###

掌握DP的基础优化方法：前缀和优化、剪去无用转移、剪去无用状态，才可以做到不写脑残的DP。

### 后注： ###

前文中的$\\mathop\{min\}\\limits\_\{i\\in S\}$和$\\sum\\limits\_\{i\\in S\}$，都表示取范围内的乘客的所有等待时间。

转载于:https://www.cnblogs.com/Hansue/p/11031721.html

[Link 1]: https://www.luogu.org/problemnew/show/P5017