显然用dp,用 $f[i]$ 表示前 $i$ 辆车过桥的最短时间,枚举上一个分组的最后一辆车 $j$ 进行转移,方程式为:
$$f[i]=min \begin{cases} f[i] \\ f[j-1]+len\div s[i] \times 60 & j<=i, \sum ^{i}_{k=j}w[k]<=wmax \end{cases}$$
其中 $tmax$ 是这一组中最长的过桥时间, $wmax$ 是桥的最大限重,$len$ 是桥的长度。
不过这题有坑,必须开long long
,而且dp数组初始化需要 $1e15$ 才能过。
ll n,m,s[1005],w[1005],w_max,len;
double f[1005];
int main()
{
w_max=read(); len=read(); n=read();
for (int i=1;i<=n;i++) w[i]=read(),s[i]=read();
for (int i=1;i<=n;i++) f[i]=1e15;
for (int i=1;i<=n;i++)
{
ll w_now=0;
double t_now=0;
for (int j=i;j;j--)
{
w_now+=w[j];
if (w_now>w_max) break;
t_now=max(t_now,60.0*len/s[j]);
f[i]=min(f[i],f[j-1]+t_now);
}
}
printf("%.1f",f[n]);
system("pause");
return 0;
}