自动搬运

查看原文

来自洛谷，原作者为

	认真的Ben **

搬运于2025-08-24 21:26:53，当前版本为作者最后更新于2019-07-23 09:11:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

【算法分析】

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

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

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

【动归方程】

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

（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：这是本人的第二篇题解（第一篇没过审核），求资磁！