Loading... [题目链接](https://www.luogu.org/problemnew/show/P1594 "题目链接") <!--more--> * * * $f\[i\]$表示前$i$辆车通过桥所需要的最短时间,$len$表示桥长度，$minx\[i\]\[j\]$表示从i到j的速度最小值，$sum\[i\]$表示前$i$辆车的重量前缀和。 - 首先$f\[i\]=len/v_i+f\[i-1\]$ - 枚举$j<i$，如果第$j$到$i$辆车可以同时通过，那么$f\[i\]=min(f\[i\],f\[j\]+len/minx\[j\]\[i\])$ * * * #### 代码如下： ```cpp #include<bits/stdc++.h> using namespace std; long long g,l,n; struct node{ long long w,s; }a[1009]; long long minx[1009][1009],sum[1009]; double dp[1009]; int main(){ cin>>g>>l>>n; for(int i=1;i<=n;i++){ cin>>a[i].w>>a[i].s; sum[i]=sum[i-1]+a[i].w; minx[i][i]=a[i].s; } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ minx[i][j]=min(a[j].s,minx[i][j-1]); } } for(int i=1;i<=n;i++){ dp[i]=(double)l/a[i].s+dp[i-1]; for(int j=i;j>0;j--){ if(sum[i]-sum[j-1]<=g) dp[i]=min(dp[i],dp[j-1]+(double)l/minx[j][i]); } } dp[n]*=60; printf("%.1lf",dp[n]); return 0; } ``` Last modification：March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏