ZJOI 仓库建设 (斜率DP)

f[i]=min(f[j]+w[j,i])+c[i];  j∈[0,i-1]

w[j,i]=p[j+1]*(x[i]-x[j+1])+...+p[i]*(x[i]-x[i]);

最裸的DP是n^2的,显然会超时

现在化简一下w[j,i]

w[j,i]=x[i]*(p[j+1]+...+p[i])-(x[j+1]*p[j+1]+...+x[i]*p[i]);

设sum[i]=sigma(p[j]*x[j]);  sump[i]=sigma(p[j]);   j∈[1,i]

那么 w[j,i]=-x[i]*(sump[i]-sump[j])-(sum[i]-sum[j])

       =-x[i]*sump[j]+sum[j]+x[i]*sump[i]-sum[i];

即 f[i]=min(-x[i]*sump[j]+sum[j]+f[j])+x[i]*sum[i]-sum[i];   j∈[0,i-1]

注意到sump[j] 和 sum[j]+f[j] 是单调递增的,可以证明决策是单调向右的。

维护一个下凸包即可。

附 DP斜率优化参考教程

①:http://wenku.baidu.com/link?url=9JNX3KG-XtAljlg1JDOIvSN_t_UntKNFdi-mDgWOh-oUEIbFQDOStyKRKXxUILxZ1CQXBJNoPzKf23IHmLtNT65peiiBoxl9vDM-G6MPsJy

②:http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html

 const maxn=;
var q,f,x,p,c,sum,sump:array[..maxn] of int64;
i,h,t,n:longint;
function kx(i,j:longint):int64;
begin
exit(sump[i]-sump[j]);
end;
function ky(i,j:longint):int64;
begin
exit(f[i]+sum[i]-f[j]-sum[j]);
end;
begin
readln(n);
for i:= to n do readln(x[i],p[i],c[i]);
for i:= to n do sump[i]:=sump[i-]+p[i];
for i:= to n do sum[i]:=sum[i-]+p[i]*x[i];
q[]:=; h:=; t:=;
for i:= to n do
begin
while (h<t) and (x[i]*kx(q[h+],q[h])>ky(q[h+],q[h])) do inc(h);
f[i]:=-x[i]*sump[q[h]]+f[q[h]]+sum[q[h]]+x[i]*sump[i]-sum[i]+c[i];
while (h<t) and ( ky(i,q[t])*kx(q[t],q[t-])<=ky(q[t],q[t-])*kx(i,q[t])) do dec(t);
inc(t);
q[t]:=i;
end;
writeln(f[n]);
end.
上一篇:oracle 12c 创建PDB用户即Local User (PDB与CDB)


下一篇:jdbc连接mysql/oracle数据库