题解 P1594 【护卫队】

· · 题解

//写写这篇题解复习动态规划

【算法分析】

乍一看这道题，以为可以用模拟来解，像这样：

带入数据一算就知道：我们错了！

仔细一看题目要求的是最短时间，这就要求我们遍历所有的可能情况。用搜索显然较繁，于是 没学过其他算法的蒟蒻 我们想到了动态规划。

【动归方程】

按照动态规划的思想方法，我们：

（1）设 f[i] 为前i辆车通过桥的最短时间，设 t[i][j] 为第i-第j辆车（租车的车队）通过所需时间；

（2）分析方程：

综合起来，我们就得到了方程：

Perfect! 但是也不要忘记了条件：

（3）其实我们也可以这样理解，对于每一辆车i，j从第i-1辆车开始倒推，看看总重是否小于最大载重量；是则能组成车队，否则不能，且前面的j-1辆车不能与i组成车队；

【细节处理】

（1）预处理重量

定义W[i]为前i辆车的总重 （即前缀和，是处理这类问题非常好的方法，可以降低时间复杂度）

需要知道第j辆车到第i辆车的总重时，用W[i]-W[j-1]就可以了；

（2）预处理时间

（值得一提的是本题解直接将时间计算出来，转为分钟，方便之后程序编写）

方法是： 定义Sb为桥的全长；v[i]为第i辆车的速度；T[i]:第i辆车通过桥所需时间；t[i][j]:第i辆车到第j辆车组成的车队通过桥所需的时间；

（3）w数组、v数组和W数组一定要开long long，否则两个较大的int相加会炸掉！

（我在这里被坑掉两个点qwq）

【代码】

#include<iostream>
#include<cstdio>
using namespace std;
long long Wb,Sb,n,w[1000],v[1000],W[1000];double T[1000],t[1000][1000],f[1000];
/*Wb:the weigh of the bridge;
  Sb:the distance of the bridge;
  w[i]:the weigh of car i; 
  v[i]:the speed of car i;
  T[i]:the time for car i to go across the bridge; (minutes)
  W[i][j]:the sum of w[i],w[i+1],...,w[j];
  t[i][j]:the time for car i,car i+1,...,car j to go across the bridge; (minutes)
  f[i]:we must spend f[i] to let car 1,car 2,...,car i to go;
  一定要开long long，否则会炸！ 
*/

int main()
{
    cin>>Wb>>Sb>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];   
        T[i]=(double)Sb/v[i]*60;
        t[i][i]=T[i];
    }
    for(int i=1;i<=n-1;i++) 
    {
        for(int j=i+1;j<=n;j++)
        {
            t[i][j]=max(t[i][j-1],T[j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        W[i]=W[i-1]+w[i];
    }   
    for(int i=1;i<=n;i++)
    {
        f[i]=T[i]+f[i-1];  //前面i-1辆车所花的时间，加上第i辆车所花时间，就是前i辆车所花时间 
        for(int j=i-1;j>=1;j--)   //倒回去查，看看能不能组成一个从j到i的车队 
        {
            if (W[i]-W[j-1]<=Wb) 
            {
                f[i]=min(f[i],f[j-1]+t[j][i]);  //cout<<f[i]<<" "; //能组成车队，比较时间 
            }
            else break;  //不能组成车队 

        }
    }
    printf("%0.1lf",f[n]); 
    return 0;
}

PS：这是本人的第二篇题解（第一篇没过审核），求资磁！