1911: [Apio2010]特別行動隊
Time Limit: 4 Sec??Memory Limit: 64 MB
Submit: 892??Solved: 359
[Submit][Status][Discuss]
Description
Input
Output
Sample 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])) do 29 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
?
)
