题解 P5017 【摆渡车】

chen_zhe · 2018-11-23 19:18:54 · 题解

考场上送我退役的题目，因为这题目没发现t4是搜索水题。

这个题如果15分钟之内写出来说明dp的水平很强了。

首先先说一下……贪心一般都能被考场上的大样例hack了，高级贪心应该也过不去。

看到没有人发记忆化搜索的方法我就补一下，代码也很简短。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>

using namespace std;

int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,m,t[505],mem[505][505];

//因为0<=st-t[i]<=m，因此可以记忆化，把这个作为状态的第二维 

int solve(int i,int st)//记忆化搜索。i：第i个人，st：开始时间st 
{
    if (i==n+1)//所有人都上车了 
        return 0;
    if (st<t[i])//如果现在的时间没有人，就到下一个人的到达时间 
        return solve(i,t[i]);
    if (mem[i][st-t[i]])//记忆化 
        return mem[i][st-t[i]];
    int sum=0,j=i;
    //车等人 
    while (j<=n && t[j]<=st)
        sum+=t[j++];
    int best=st*(j-i)-sum+solve(j,st+m); 
    //人等车
    for (;j<=n;j++)
    {
        sum+=t[j];
        best=min(t[j]*(j-i+1)-sum+solve(j+1,t[j]+m),best);
    }
    return mem[i][st-t[i]]=best;
}

int main()
{
    //memset(mem,-1,sizeof(mem));
    n=read(),m=read();
    for (int i=1;i<=n;i++)
        t[i]=read();
    sort(t+1,t+n+1);//显然从小到大按照时间排序更好算 
    cout << solve(1,0) << endl;
    return 0;
}