LA3983 Robotruck

虫洞

单调队列优化DP,感觉比较套路?
上不去Vjudge,也懒得打就随便口胡一下。
sxy大佬要是您看的我要是扯淡麻烦提醒我一下QAQ

sum[i]表示从0到i依次走的距离,sg[i]表示1~i的重量和,dis[i]表示从0到i直接走的距离。
f[i]=min(f[j]+sum[i]-sum[j]+dis[i]);
=min(f[j]+sum[j])+sum[i]+dis[i]; (sg[j]>=sg[i]-C)
发现sg[j]是单调增的。
用单调队列维护一个f[i]+sum[i]单减且sg[i]单增的值。

原文地址:https://www.cnblogs.com/Achenchen/p/7612627.html