BZOJ 1010 [HNOI2008]玩具装箱toy 【斜率优化】

tonyfang posted @ 2016年8月01日 15:17 in BZOJ with tags c++ OI , 480 阅读

【题解】

首先dp方程很好列出,$f_{i} = min(f_{j} + (i-j-1 + s[i] - s[j] - L)^{2})$,很明显这是$O(n^2)$的,下面我们尝试优化它。

首先我们令$g_{i} = s_{i}+i, C=1+L$

那么$f_{i} = min(f_{j} + (g_{i}-g_{j}-C)^{2})$

 

1. 我们证明状态影响的持续性

假设现在有两个决策点可以转移,$f_{j}, f_{k}$,假设$j<k$,且决策$k$比$j$

$f_{j} + (g_{i}-g_{j}-C)^{2} >= f_{k} +(g_{i} - g_{k} -C)^{2}$

那么对于$i$后的状态$T$,$f_{t} = f_{i}+V$; 

只要证明 

$f_{j} + (g_{t}-g_{j}-C)^{2} >= f_{k} +(g_{t} - g_{k} -C)^{2}$

$f_{j} + (g_{t}-g_{j}-C+V)^{2} >= f_{k} +(g_{t} - g_{k} -C+V)^{2}$

$f_{j} + (g_{i}-g_{j}-C)^{2} + V^{2} + 2V(g_{i} - g_{j} - C) >= f_{k} +(g_{t} - g_{k} -C)^{2} + 2V(g_{i} - g_{k} - C)$

那么很明显推出就是要证明:

$g_{i} - g_{j} -C$ >= $g_{i}-g_{k}-C$

那么$g_{j} <= g_{k}$,显然满足要求,所以状态有持续影响。

2. 求斜率方程

$f_{j} + (g_{i}-g_{j}-C)^{2} >= f_{k} +(g_{i} - g_{k} -C)^{2}$

$f_{j} + g_{i}^{2} + (g_{j}+C)^{2} - 2g_{i}(g_{j}+C) >= f_{k} + g_{i}^{2} + (g_{k}+C)^{2} - 2g_{i}(g_{k}+C)$

$f_{j}-f_{k} + (g_{j}+C)^2 - (g_{k}+C)^2 >= 2g_{i}(g_{j}-g_{k})$

$\frac{(f_{j}+(g_{j}+C)^2) - (f_{k} + (g_{k}+C)^2)}{2g_{j} - 2g_{k}} <= g_{i}$

是不是觉得特别眼熟?没错!就是斜率!

令$s_{i} = f_{i}+(g_{i}+C)^2, t_{i} = 2g_{i}$,那么$\frac{s_{k}-s_{j}}{t_{k}-t_{j}} <= g_{i}$

斜率小于等于一个定值?

再清晰一点,设$X(i, j)$表示i到j的斜率,那么$X(k, j) <= g_{i}$

也就是说,如果$X(k, j) <= g_{i}(j<k)$,那么说明k比j优。

那么这说明了什么呢?我们就可以用一个队列维护了!

 

3. 规定队列维护的规则

类似于维护一个凸壳作为决策,那么我们就要规定队列如何维护了

每次取出队首作为决策

A. 队首维护规则

假设$x, y(x<y)$为队首元素,若$X(y, x) <= g_{i}$,那么说明y比x优秀,把x扔掉。否则不需要维护

B. 队尾维护规则

维护一个斜率单调上升的队列,那么每次从队尾删去元素即可。

注意要点:由于$f_{i}$是单调上升的!!!

 

# include <stdio.h>
using namespace std;

int n;
long long C, s[50010], g[50010], f[50010], q[200010], head, tail;


inline double X(int i, int j) {
	return (f[i] - f[j] + (g[i]+C)*(g[i]+C) - (g[j]+C)*(g[j]+C))/(2.0*(g[i] - g[j]));
}

int main() {
	scanf("%d%lld", &n, &C); ++C;
	for (int i=1, x; i<=n; ++i) {
		scanf("%d", &x);
		s[i] = s[i-1] + x;
		g[i] = s[i] + i;
	}
	head=1, tail=0;
	q[++tail]=0;	
	for (int i=1; i<=n; ++i) {
		while(head<tail && X(q[head], q[head+1]) <= g[i]) ++head;
		f[i] = f[q[head]] + (g[i] - g[q[head]] - C)*(g[i] - g[q[head]] - C);
		while(head<tail && X(q[tail-1], q[tail]) > X(q[tail], i)) tail--;
		q[++tail] = i;
	}
	printf("%lld\n", f[n]);
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter