--------------------------------------------------------------------------------
好难啊..QAQ
昨天我和shy说要难一点,结果今天就成这样了...
[Apio2010]特别行动队
2015年7月10日 21:20
这是道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))
