Luogu P1594 护卫队

题目链接


$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])$


代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
}
# dp

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×