[codeforces 321E]Ciel and Gondolas

题目链接

http://codeforces.com/problemset/problem/321/E

题目大意

n个人,k条船,互相不认识的人坐在一条船有个不舒适程度a_{i,j},最小化每条船的不舒适程度总和,其中n\leq4000,k\leq800

Solution

f(i,j)表示前i个人分配到j条船的最小花费

f(i,j)=min\begin{Bmatrix}f(k,j-1)+calc(i->k+1)\end{Bmatrix}

直接暴力算的时间复杂度是O(n^{5}),有什么办法加速呢?

首先我们发现calc占了n^{2},考虑优化calc,怎么优化?增量法

w[i,j]表示calc(i->j),先维护列的前缀和,再整体类似倒三角形的计算,画个图示意下

相同颜色即为我们需要维护的列的前缀和,这样计算w数组时间复杂度为O(n^{2})

这样原方程式可化为

f[i,j]=min\begin{Bmatrix}f[k,j-1]+w[k+1,i]\end{Bmatrix}

根据a的非负性,上式的w显然满足四边形不等式

这题本来我写了一下午单调队列+二分的做法,但是发现决策与船划分的一致性根本无从下手,搜了下题解,发现整体二分正好可以很好的弥补这个缺点,然后就写了个整体二分,然后就耿直的TLE了。

于是我卡常卡了一小时,还是TLE,后来才发现,居然要读写挂QQ图片20160623113034

空间上其实可以滚动一维,然而这并没有什么卵用

 

发表评论