Earthson's Blog

2010吉林省赛E题Warehouse and Truck。卡车在仓库装了货物，送到各个商店（ 所有点都在一条直线上），耗费是当前载重量乘以距离（在每个商店卸下货物之后载重量发生变化）。

比赛的时候没找到算法，这题郁闷很久，一直到现在^^其实想想，当初比赛的时候连什么是DP都不知道。当时在数学上还有些癖好——根本无视递推，当时的我看来，只有通项才是有意义的-_-!确实太固执。。。
当然，我还是找到了解的形式：

显然，一旦到达一个端点，它应该一路直冲到另一端。在到达端点之前，有各种折返，但是可以确定每次折返都是越过仓库的（如果它折回来，必然是越过仓库以后再折回去的）。如上所说，这都是显然的。。。其实依照这些就可以很快导出递推，只不过当时的我对递推很不敏感，这真是杯具。

首先，折返必然是穿越仓库(x=0)的。我们令i表示仓库左边的点，j表示仓库右边的点（我想我不需要用太多晦涩难懂的数学语言来描述这一点），
我们用表示遍历i,j范围内所有点，但不越出这个范围的最优开销（其实就是一个小的子问题，去掉了i到j外的所有点）。当然这是不够的，根据上面的解的形式，最优解必然在到达一个端点（i或者j）之后，直接转到另一个。我们需要区分两种情况：然后这确实足够了

因为从i到j最优解必然是的最优解末端往右到j。同样，对称的，可以得到j到i的，这样就得到了。

这个递推，虽然描述简单，求起来却很麻烦。鉴于式子过长,代码就不贴了，因为我自己看起来都够呛（表达式很长）。这样的递推时间上是的，其实因为是对分的，所以常数很小^^

想了下，还是把状态方程写出来。我们令为i到j的距离，令为剩余货物的量（就是i到j所有点的货物全部卸下之后剩下的货物），于是，我们有以下方程：

***如果递推特征不是很明显的话，或许分析解的特征，可以找到更多思路