题目意思我就不多说了。
基本的DP很容易想到的。
设f[i]为前i个玩具放到箱子里面的最小代价。
int a = sum[i] - sum[j] + i - j - 1 - L;
那么f[i] = min(f[j] + a * a);
但是这样去转移的话需要n^2的复杂度。。这样的话就会TLE。
这里的话我们就可以应用到单调性优化或者斜率优化。
先了解一下单调性优化可以用在什么地方。
我们可以证明出对于任意的一个i，他的决策点是j，为了保持最优解，那么在i从1到n的过程中，每一个状态的决策点j都是不下降的。
怎么证明这里就不说了。
然后说一下具体的单调优化的方法
先讲一下几个数组的意思，sta[i]代表第i个状态(也就是f[i])转移的决策点的编号(编号就是第几大)
l[sta[i]]代表这个决策点编号决策的状态的区间左边节点
for(int i = 1 ; i <= n ; ++i)首先枚举i
然后利用二分查找
int find(int x)
{
int left = 1 , right = r , mid = (left + right) /
2;
while(left <= right)
{
if(l[sta[mid]] == x) return
mid;
if(l[sta[mid]] < x) left = mid + 1;
else right = mid -
1;
mid = (left + right) / 2;
}
return right;
}
我也不知道怎么描述这个呀。。。大概就是查找i在哪个决策点的区间里。
然后根据编号转移。
接着需要动态的更新sta中其他点的决策点
找到大概在哪个区间，然后对这个区间再二分找具体的某个点
然后更新就ok了
|
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62 |
#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <iostream>#define mod 9999973#define N 50005#define ll long longusing
namespace std;int
n , L , c[N] , l[N] , sta[N] , left , right , r;ll sum[N] , f[N];ll turn(int
j , int
i){ ll x = i - j + sum[i] - sum[j] - 1; return
f[j] + (x - L) * (x - L);}int
find(int
x){ int
left = 1 , right = r , mid = (left + right) / 2; while(left <= right) { if(l[sta[mid]] == x) return
mid; if(l[sta[mid]] < x) left = mid + 1; else
right = mid - 1; mid = (left + right) / 2; } return
right;}void
work(){ scanf("%d%d", &n, &L); for(int
i = 1 ; i <= n ; ++i) scanf("%d", &c[i]) , sum[i] = sum[i - 1] + c[i]; for(int
i = 1 ; i <= n ; ++i) l[i] = n + 1; memset(sta , 255 , sizeof(sta)); l[0] = 1 , sta[1] = 0 , r = 1; for(int
i = 1 ; i <= n ; ++i) { f[i] = turn(sta[find(i)] , i); while(r && l[sta[r]] > i && turn(i , l[sta[r]]) < turn(sta[r] , l[sta[r]])) --r; if(!r) { sta[++r] = i; l[i] = i; continue; } int
left = l[sta[r]] , right = n , mid = (left + right) / 2; while(left <= right) { if(turn(i , mid) > turn(sta[r] , mid)) left = mid + 1; else
right = mid - 1; mid = (left + right) / 2; } if(turn(i , left) > turn(sta[r] , left)) continue; sta[++r] = i , l[i] = left; } printf("%lld\n", f[n]);}int
main(){ work(); return
0;} |
原文：http://www.cnblogs.com/lalawu/p/3561079.html