1911: [Apio2010]特别行动队

Time Limit: 4 Sec  Memory Limit: 64 MB

Submit: 892  Solved: 359

[][][]

DescriptionInputOutputSample Input4

-1 10 -20

2 2 3 4 Sample Output9HINT

Source

_________________________________________

很简单的动规方程： F[i]:=max(F[j]+a*(s[i]-s[j])^2+b*(s[i]-s[j])+c)

用斜率式优化：  

   原方程展开：      F[i]:=max(F[j]+a*s[i]^2-2*a*s[i]*s[j]+a*s[j]^2+b*s[i]-b*s[j]+c)

   设g(i,j)为  F[i] 的一个决策

            则  g(i,j)-g(i,k)=f[j]+a*s[j]^2-(f[k]+a*s[k]^2)-(b+a*s[i]^2)*(s[j]-s[k]) 

           当 决策j 优于决策 k时  g(i,j)-g(i,k)>0        

            设 y[i]=f[i]+a*s[i]^2  , x[i]=s[i]

           所以可化简为      (y[k]-y[j])/(x[i]-x[j])>b+a*s[i]^2   

            因为 a<0 所以  b+a*s[i]^2 单调递减。

_________________________________________

 

1 ProgramStone;  2 var i,j,head,tail,a,b,c,n:longint;     s,f,cons,sq,que:array[0..1000001]ofint64;   3 function delhead(i,j,k:longint):boolean;   4 begin   5     if cons[i]*(s[j]-s[k])>sq[j]-sq[k] then   6         exit(true)                                      7     else 8         exit(false);    9 end; 10 functiondeltail(i,j,k:longint):boolean;   11 begin    12     if(sq[i]-sq[j])*(s[j]-s[k])>(sq[j]-sq[k])*(s[i]-s[j])     13     then exit(true)                                                                    14     else exit(false);   15 end; 16 functionmax(a,b:int64):int64;   17 begin    18 ifa>b thenmax:=a elsemax:=b;   19 end;20 Begin  21 readln(n);   22 readln(a,b,c);   23 fori:=1ton do   read(s[i]);   24 fori:=2ton do   inc(s[i],s[i-1]);   25  head:=1;tail:=0;  26  fori:=1ton do   27 begin     28 cons[i]:=b+2*a*s[i];      while(tail>head)and(delhead(i,que[head],que[head+1])) do29 inc(head);      30 j:=que[head];      31 f[i]:=max(a*sqr(s[i])+b*s[i]+c,f[j]+a*sqr(s[i]-s[j])+b*(s[i]-s[j])+c);      32 sq[i]:=f[i]+a*sqr(s[i]);      while(tail>head)and(deltail(i,que[tail],que[tail-1])) dodec(tail);      inc(tail);      33 que[tail]:=i;    34 end;  35  writeln(f[n]);36  end.37 38