一看就是dp

设前i个的最小代价为dp[i]
dp[i]=min{
     dp[j]+sum(j+1,i)-(j-j)*x[j+1]
}

不过，这么裸交上去是要tle的。
若计算dp[i]时，从dp[a]转移的值不如从dp[b]转移的值，又a<b，则以后永远不用考虑从a转移了。
为了把时限压到线性或nlogn，要针对上面这个特点用凸单调性优化。
用一个双端队列来维护可以考虑的转移方法。
每次计算，
1.while 队头的备选状态比他后面的差，删除之。
2.用队头的状态计算新的dp值
3.新的dp值压入队尾
4.while 队尾的备选状态超越他前面一个的时间小于他前面的超越前面的前面的时间，删除他前面一个的状态

计算一个状态a超越一个状态b的时间，可以推公式：
crossTime(b,a)
	dt=dat[b+1]-dat[a+1]
	ret=-dp[a]+dp[b]-s[b]+s[a]-a*dat[a+1]+b*dat[b+1]
	if dt==0
                if ret<=0 return b+K
                else return N
	ret=(ret+dt-1)/dt
	if ret<b+K
                  ret=b+K;
	return ret
也可以用2分查找。
实践证明，这两种方法时间差不多（200ms左右）

比较阴险的是必须用long long才能ac
比赛的时候一定不能有这种欺负C++选手的题！

• Re:雁过留声——凸单调性优化 根据楼上大牛的描述，写了详细的结题报告 (87) prowind 2009-07-24 13:47:42
  • O(n)的跑得好慢啊 (10) tracyhenry 2009-07-25 14:51:09
• 这题怎么欺负C++选手了。。。。 (0) baiqi2piao 2009-09-16 01:20:24