7.4测试总结

--------------------------------------------------------------------------------
好难啊..QAQ
昨天我和shy说要难一点,结果今天就成这样了...
 

[Apio2010]特别行动队

 
这是道DP斜率优化的模板题啊...
首先很容易得出朴素的DP状态转移方程如下:
f(i) = max{f(j) + g(S(i) - S(j))} (0 < j < i)
其中,g(x) = a*x^2 + b*x + c  ,  S(i) = Σ(k = 1,i)xk
展开、化简之后得:
f(i) = max(f(j) + a*S(j)^2 - b * S(j) - 2*a*S(i)*S(j)} + g(S(i))