Description:


Input:


Output:


Sample Input:


Sample Output:


HINT:


题解:


第一次做斜率优化的题诶,之前都不知道斜率优化是什么~

\(dp[i]\) 为前i个士兵的答案,可以很容易地看出这一题的DP方程:

\(dp[i] = max(dp[i], dp[j]+(sum[i]-sum[j])^2\times a +(sum[i]-sum[j])\times b + c)\)

\(k ,若j比k要优,可以推导出如下式子:

\(\frac{dp[j]-dp[k]+(sum[j]^2 - sum[k]^2)\times a - (sum[j]-sum[k])\times b} {2\times (sum[j]-sum[k])} \gt sum[i]\)

然后可以得出单调性,用单调队列维护一下就可以了。