抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

例题1: P2365 任务安排 我知道你们会n2n^2n2大暴力,也会O(n)O(n)O(n)普通斜率优化,但是不妨提高一下我们的姿势水平,假设1≤N≤1000001 \le N \le 1000001≤N≤100000,而且TiT_iTi​和CiC_iCi​不一定是正整数。 朴素dpdpdp方程:dp[i]=dp[j]−(s+sumt[i])×sumc[j]+sumt[i]×sumc[i...

首先上一道例题: HDU3507 给你一个序列,你可以把这个序列分成若干段,每段的花费是(∑i=1kC[i])2+M(\sum _{i=1} ^k C[i])^2 +M(∑i=1k​C[i])2+M 考虑朴素的n2n^2n2方程,dp[i]=min⁡(dp[j]+M+(sum[i]−sum[j])2)dp[i]=\min(dp[j]+M+(sum[i]-sum[j])^2)dp[i]=min...