题目大意是有k个伞兵落到地面上，已知每个人落点的概率，有m个物资站，落地后要去最近的站。问如何安排这些物资站，使得伞兵落地后行走的期望距离的和最小。（所有落点最多1000个）。
显然是个dp题，我们可以先预处理下，对每个落点点求出他的概率总和，代表伞兵落在这点的权。可以直到物资站一定悬在伞兵落下的那些点上，所以我们就可以用$dp_{ij}$ 表示前$i$个落地点中选择$j$个作为物资点，则很容易想到转移方程$dp_{ij}=min(dp_{kj_{1}}+dis_{ki})$，其中$j_{1}=j+1$, $dis_{ki}$表示在$[k,i]$区间的落地点选则一个作为物资点所走距离最小值的期望(就是每点到物资点的距离乘该点概率的总和)。
现在关键就是求$dis$，其实我们注意到 假设对于$[i,j]$，假设选取$k$作为物资点，则有
$dis_{ij}=\sum_{n=i}^{k}{(a_{k}-a_{n})p_{n}} + \sum_{n=k+1}^{j}{(a_{n}-a_{k})p_{n}}$
而若选择$k+1$作为物资点，则有
$dis_{ij}^{‘}=\sum_{n=i}^{k}{(a_{k+1}-a_{n})p_{n}} + \sum_{n=k+1}^{j}{(a_{n}-a_{k+1})p_{n}}$
则相减并化简得
$dis_{ij}^{‘}-dis_{ij}= (a_{k_{1}}-a_{k})(\sum_{n=i}^{k}{p_{n}} - \sum_{n=k+1}^{j}{p_{n}}) = (a_{k_{1}}-a_{k})(sum_{ik}-sum_{k_{1}{j}})$
设$tmp=dis_{ij}^{‘}-dis_{ij}$,$sum$可以很容易求出，这样很显然，当$k$增加时，$tmp$的值也在增加，所以，若选取$k$作为物资点，则要$tmp \geq 0$，否则我们可以选取$k+1$作为物资点，这样，可以对$dis$进行预处理，然后就可以得出答案
1 |
|