BZOj1010 [HNOI2008]玩具装箱toy

dp[i]=min(dp[j]+(sum[i]sum[j]+ij1L)2)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)dp[i]=min(dp[j]+(A[i]-A[j]-c)^2)
(A[i](A[j]+c))2=A[i]2+(A[j]+c)22A[i](A[j]+c)(A[i]-(A[j]+c))^2 = A[i]^2 + (A[j]+c)^2 - 2*A[i]*(A[j]+c)
得到
dp[i]=min(dp[j]+A[i]2+(A[j]+c)22A[i](A[j]+c))dp[i] = min(dp[j]+A[i]^2 + (A[j]+c)^2 - 2*A[i]*(A[j]+c))

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

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

dp[j]+A[i]2+(A[j]+c)22A[i](A[j]+c)<dp[k]+A[i]2+(A[k]+c)22A[i](A[k]+c)dp[j] + A[i]^2 + (A[j]+c)^2 - 2*A[i]*(A[j]+c) < dp[k] + A[i]^2 + (A[k]+c)^2 - 2*A[i]*(A[k]+c)
dp[j]+(A[j]+c)22A[i](A[j]+c)<dp[k]+(A[k]+c)22A[i](A[k]+c)dp[j] + (A[j]+c)^2 - 2*A[i]*(A[j]+c) < dp[k] + (A[k]+c)^2 - 2*A[i]*(A[k]+c)
2A[i](A[k]+cA[j]c)<dp[k]dp[j]+(A[k]+c)2(A[j]+c)22*A[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]<0A[i]>0 ,A[k]-A[j]<0
2A[i](A[k]A[j])<dp[k]dp[j]+(A[k]+c)2(A[j]+c)22*A[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]2A[j]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)2y[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<jk < j且$g[k,j] <= A[i] ,那么k不如j$优

相当于如果存在j,kj,k
如果对于决策ii
满足i>j>ki > 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[i,j]>g[j,k]
如果g[j,k]<=A[i]g[j,k]<=A[i],那么j无用
如果g[j,k]>A[i]g[j,k]>A[i],那么
g[i,j]<g[j,k]>A[i]g[i,j] <g[j,k]>A[i]jj无用。
因此,单调队列还需要维护队尾

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]);
}
文章目录