[bzoj3675]-[Apio2014]序列分割

斜率优化……

比什么圆锥曲线好算多了QAQ

题目(BZOJ)

洛谷要输出方案数……在此我就不贴链接了。

 

这题先写dp方程:dp[i][j]表示第i次操作对前j个元素的最大得分。

方程很好写:

dp[i][j]=max(dp[i][j],dp[i-1][k]+sum[k]*(sum[j]-sum[k])), 0<=k<j

而由于这题要开long long,内存只有128M,所以加个滚动数组,ok。

然后就是斜率优化套路了……

发表评论