【Codeforces 553E】Kyoya and Train

首先可以想到一个dp:令\(f_{x,t}\)表示在\(t\)时间到达\(x\),再到终点的最小期望代价,那么有

$$f_{x,t}=min(G_{e,t}=val_e+\sum_{k=1}^{t}p_{e,k}f_{to_e,t+k})$$

其中\(e\)为\(x\)的出边。

那么进行分治FFT,对于一个时间区间\([l,r]\),先计算\([m+1,r]\),再计算\([m+1,r]\)对\([l,m]\)的贡献,最后再计算\([l,m]\)。

对于右边对左边的贡献,显然可以FFT加速计算。当递归到最底层时,可以直接用上式计算\(f\)的值。

这道题要手写复数类否则会被卡常。。

说点什么

您将是第一位评论人!

提醒
wpDiscuz