P5017 摆渡车

Forever丶CIL · 2018-11-17 22:29:29 · 题解

介绍一个并没有很好的方法，复杂度O(n^2m)比很多人慢了点，实测380ms

具体思路是这么来的：

首先我想用A[i]表示把前i个人运到人大，前i个人一共要等的时间。
那么我口胡了一个转移：A[i]=min(A[j]+Wait[j+1][i]+extra)，指的就是前j个人已经运到人大了，从j+1到i这些人坐一趟车去人大。
这里的Wait[a][b]表示从a到b的人坐一趟车，a到b这些人一共要等多久，至于还要加一个extra，是因为车在第j个人到达时出发，当地i个人来了，车也许还没回来，你还要再等一会，让车回来，这段时间的等待，就是extra。

感觉思路好像很严密的样子，草草写完一交，却发现只拿了55分。

问题出现在哪里？

假设错误 \rightarrow 我误以为第车一定会在第j个人来到的时候开出，但实际上车都不一定会在第i个人来的时候开出（因为车可能还在路上）
边界要注意，t[0]赋初值为-Inf

这样分析之后，我们优化一下思路：

A[i][j]表示前i个人已经被运到人大了，并且第i个人到等车的地方之后又过了j秒车才开，这样的情况的最优解。
这样我们分两种情况：
1. 第j个人到了以后，等了k秒，发车，之后i来了，且此时车回来了，此时转移为： A[i][0]=min(A[i][0],A[j][k]+Wait[j+1][i]);
2. 第j个人到了以后，等了k秒，发车，之后i来了，但是车还没回来，此时转移为：A[i][k+m+t[j]-t[i]]=min(A[i][k+m+t[j]-t[i]],A[j][k]+Wait[j+1][i]+(i-j)*(k+m+t[j]-t[i]));

最终答案就在A[n][i]中取个min就好了，i\in [0,m]

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define debug(x) cout<<#x<<"="<<x<<endl
typedef long long ll;
using namespace std;
const int Inf=0x3f3f3f3f;
const int Maxn=1000;
const int Maxm=200;
int n,m;
int t[Maxn];
int A[Maxn][Maxm];
int Wait[Maxn][Maxn];
inline int read()
{
    int rt=0,fl=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') fl=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){rt=rt*10+ch-'0';ch=getchar();}
    return rt*fl;
}
void read_ini()
{
    memset(A,0x3f,sizeof(A));
    n=read(); m=read();
    for(int i=1;i<=n;i++) t[i]=read();
    sort(t+1,t+1+n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++) 
            for(int k=j;k<=i;k++) Wait[j][i]+=t[i]-t[k];
    for(int i=0;i<=m;i++) A[1][i]=i,A[0][i]=0;
    t[0]=-Inf;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<i;j++)
        {    
            for(int k=0;k<=m;k++)
            {
                if(k+m+t[j]<=t[i])
                {
                    A[i][0]=min(A[i][0],A[j][k]+Wait[j+1][i]); 
                }
                else
                {
                    A[i][k+m+t[j]-t[i]]=min(A[i][k+m+t[j]-t[i]],A[j][k]+Wait[j+1][i]+(i-j)*(k+m+t[j]-t[i]));
                }
            }
        }
    }
    int ans=Inf;
    for(int i=0;i<=m;i++) ans=min(ans,A[n][i]);
    printf("%d\n",ans);
}
int main()
{
    read_ini();
    return 0;
}

整体来说，题目难度不是很大，但是细节比较多，需要更细心一点，祝大家RP++