CodeForces 660F

谁践踏了优雅 2022-01-28 09:37 287阅读 0赞

题意：给定一段数列，现在叫你取其中一段，第一位*1，第二位*2…求最大。

思路：sum[n]=a[1]+a[2]+…a[n]，原先的dp[n]=a[1]*1+a[2]*2+a[3]*3+..a[n]*n;

那么现在的max[i]=max:dp[i]-dp[j]-(sum[i]-sum[j])*j; =-sum[i]*j+j*sum[j]-dp[j]+dp[i] 可以斜率优化，由于K=sum[i]并不是单调递增的，所以我们维护凸包不能弹出队首，而需要二分。

参考：https://www.e-learn.cn/content/qita/847104

发表评论

表情：
评论列表 （有 0 条评论，287人围观）

还没有评论，来说两句吧...

相关阅读

    相关 CodeForces 1200F

    题意略。 思路： 如果是问一下然后搜一下，那必然是不现实的。因此我们要预处理出所有的答案。 我们令mod = lcm(m1,m2,...,mn)。可知，在任意一点，我们挑

    缺乏、安全感缺乏、安全感/ 0 赞/ 247 阅读