BZOJ 1010

发表于 |

题目

有$N$个玩具，每个玩具长度为$c_i$ 。现在要把玩具全放到若干个箱子里，要求每个箱子里的玩具编号连续，并且任意$2$件玩具间都要有$1$个单位的空隙。即，对于装了编号为$[i,j]$的玩具的箱子，箱子的长度必须恰好为$j−i+\sum_{i≤k≤j}c_k$。而做一个长度为$x$的箱子所需的费用为$(x−L)^2$ ，$L$为常数。求最小的费用。

数据范围

$1\leq N \leq 50000 \quad 1\leq L,c_i \leq 10^7$

做法

我们发现，除了给定的参数外，费用只和有几个玩具有关，于是，DP状态和转移方程如下：

$dp[i]=$将前$i$个玩具放入箱子中的最小费用
$dp[0] = 0$
$dp[i]=min_{0\leq j < i}(dp[j] + (i-j-1+\sum_{j<k\leq i}c_k-L)^2)$

直接用此方程递推，复杂度是$O(N^2)$ （将求和用前缀和优化后）。考虑将方程等价变形。

$dp[i]=min_{0≤j<i}(dp[j]+((i+S[i])−(j+1+L+S[j]))^2)$
$dp[i]=min_{0≤j<i}(−2(i+S[i])(j+1+L+S[j]))+(i+S[i])^2+(j+1+L+S[j])^2+dp[j])$

显然，这个DP方程可以用斜率优化。

$a[i]:=−2(i+S[i])$
$b[i]:=i+1+L+S[i]$
$d[i]:=(i+1+L+S[i])^2$

对于决策$j,k(j<k)$，$j$不会称为较差的决策的必要条件为：$a[i]\times b[j]+d[j]\leq a[i]\times b[k]+d[k]$，即：$−a[i]\leq \frac{d[k]−d[j]}{b[k]−b[j]}$。对于决策$x,y,z(x\leq y\leq z)$，易证：若有$k_{xy}\geq k_{yz}$，则$y$不会是较优的。

于是，我们维护一个决策组成的下凸壳。又由于$−a[i]$单调递增，所以可以用双端队列来维护下凸壳。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 50005;
int N, deq[MAX_N];
ll C[MAX_N], S[MAX_N], dp[MAX_N], L;
inline bool check(int j, int k, int l)
{
	ll b1 = j + 1 + L + S[j], d1 = b1 * b1 + dp[j];
	ll b2 = k + 1 + L + S[k], d2 = b2 * b2 + dp[k];
	ll b3 = l + 1 + L + S[l], d3 = b3 * b3 + dp[l];
	return (d2 - d1) * (b3 - b2) >= (d3 - d2) * (b2 - b1);
}
ll f(int i, int x)
{
	ll tmp = x - i - 1 + S[x] - S[i] - L;
	return dp[i] + tmp * tmp;
}
void solve()
{
	S[0] = 0;
	for (int i = 0; i < N; ++i) S[i + 1] = S[i] + C[i];
	dp[0] = 0;
	int s = 0, t = 1;
	deq[0] = 0;
	for (int i = 1; i <= N; ++i) {
		while (t - s > 1 && f(deq[s], i) >= f(deq[s + 1], i)) s++;
		dp[i] = f(deq[s], i);
		while (t - s > 1 && check(deq[t - 2], deq[t - 1], i)) t--;
		deq[t++] = i;
	}
	printf("%lld\n", dp[N]);
}
int main()
{
	cin >> N >> L;
	for (int i = 0; i < N; ++i) scanf("%lld", C + i);
	solve();
	return 0;
}