1.9测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
ZJOI2010..
--------------------------------------------------------
T1:
见这个
--------------------------------------------------------
T2:
跑一个最大流
然后在残余网络上加边：复制一遍原来的边，容量改为inf,费用改为扩容的费用
另外新建汇点，从原来的汇点向新汇点连边，容量为k，费用为0
跑费用流即可
--------------------------------------------------------
T3：
考虑DP:f(i,j)第i个，已经建了j个基站了，并且第i个点一定要建
转移:f(i,j) = min{f(q,j-1)+cost(q,i)}
其中cost(q,i)表示q，i两点有基站，[q,i]中其他点都没有基站，所有没被覆盖的点的赔偿费用之和
这样就有40分啦
然后，考虑枚举j,再枚举i
在一个线段树中存一下f(q,j-1)+cost(q,i)
询问一下最小值就好啦
f(q,j-1)倒是好办，上一次弄完加进去就行了，cost(q,i)呢？
考虑，当得到f(i,j)后，如果要在i后面的点建基站
那么右界刚好为i的村庄坑定是要被覆盖了
当然前提是它的左界以内也没有建基站
因此在线段树中[1,l-1]的部分加一个赔偿费用，表示如果要从这些点转移，是要赔偿的
然后复杂度就是O(n*k*lgn)的
--------------------------------------------------------
评论 (0)
