BZOj1010 [HNOI2008]玩具装箱toy

$dp[i]=min(dp[j]+(sum[i]-sum[j]+i-j-1-L)^2)$

$dp[i]=min(dp[j]+(A[i]-A[j]-c)^2)$
$(A[i]-(A[j]+c))^2 = A[i]^2 + (A[j]+c)^2 - 2A[i](A[j]+c)$
得到
$dp[i] = min(dp[j]+A[i]^2 + (A[j]+c)^2 - 2A[i](A[j]+c))$

其中c > 0
A满足单调递增

决策j比k优,且j在k的右边

$dp[j] + A[i]^2 + (A[j]+c)^2 - 2A[i](A[j]+c) < dp[k] + A[i]^2 + (A[k]+c)^2 - 2A[i](A[k]+c)$
$dp[j] + (A[j]+c)^2 - 2A[i](A[j]+c) < dp[k] + (A[k]+c)^2 - 2A[i](A[k]+c)$
$2A[i](A[k]+c-A[j]-c) < dp[k]-dp[j] + (A[k]+c)^2 - (A[j]+c)^2$
其中$A[i]>0 ,A[k]-A[j]<0$
$2A[i](A[k]-A[j]) < dp[k]-dp[j] + (A[k]+c)^2 - (A[j]+c)^2$
$A[i]>((dp[k]+ (A[k]+c)^2 - (dp[j]+(A[j]+c)^2)) / (A[k]2-A[j]2)$

设$y[i] = dp[i] + (A[i]+c)^2$
设$x[i] = A[i] * 2 $

$A[i]>((y[k] - y[j]) / (x[k]-x[i])$
设$g[k,j] = (y[k]-y[l]) / (x[k]-x[l])(其分母大于0)$

如果存在$k < j$且$g[k,j] <= A[i] $,那么$k$不如$j$优

相当于如果存在$j,k$
如果对于决策$i$
满足$i > j > k$
如果存在$g[k,j] <= A[i] $
若$g[j,i]<=A[i]$
则$i$比$j$优秀,$j$比$k$优秀,$k$无用。
若$g[j,i]>A[i] $
即$g[i,j]<=A[i] $
则$i$不如$j$优秀,又k不如j优秀,所以k无用。
故如果存在$k < j$且$g[k,j] <= A[i]$ ,那么k无用
另外
如果$g[i,j]>g[j,k]$
如果$g[j,k]<=A[i]$,那么j无用
如果$g[j,k]>A[i]$,那么
$g[i,j] <g[j,k]>A[i]$,$j$无用。
因此,单调队列还需要维护队尾

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define sqr(x) ((x)*(x))
const int maxn = 50050;
using namespace std;
typedef long long LL;
LL N,L,c,dp[maxn],A[maxn];
double g(LL j,LL k){
double yj,yk,xj,xk;
//满足j<j
yj = dp[j] + sqr(A[j]+c);
yk = dp[k] + sqr(A[k]+c);
xj = A[j] * 2;
xk = A[k] * 2 ;
return 1.0*(yj-yk)/(xj-xk);
}
LL front,rear,q[maxn];
int main(){
scanf("%lld%lld",&N,&L);
c = 1+L;
A[0] = 0;
for (int i=1;i<=N;i++){
int c;
scanf("%lld",&c);
A[i] = A[i-1] + c;
}
for (int i=0;i<=N;i++)A[i] += i;
memset(dp,0x3f,sizeof(dp));
dp[0] = 0;
front = rear = 0;
q[rear++] = 0;
for (int i=1;i<=N;i++){
while (rear-front>=2 && g(q[front],q[front+1]) <= A[i]) front++;
int j = q[front];
dp[i] = dp[j]+sqr(A[i]-A[j] - c);
while (rear-front>=2 && g(q[rear-2],q[rear-1])>g(q[rear-1],i)) rear--;
q[rear++] = i;
}
printf("%lld\n",dp[N]);
}
文章目录
|