社区讨论

求助：对这题斜率优化后的滚动数组有点疑惑

1190040257a
P3648[APIO2014] 序列分割参与者 2已保存回复 7

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@lodcz1sc
此快照首次捕获于
2023/10/31 04:34
2 年前
此快照最后确认于
2023/11/06 19:56
2 年前
查看原帖
这题状态转移方程是

f[i][j]=max(f[i−1][k]+(sum[j]−sum[k])∗sum[k])f[ i][j]=max(f[i-1][k]+(sum[j]-sum[k])*sum[k])

sum为前缀和嘛，按理说把第一维压掉后应该跟01背包一样，jj从NN到11，j−−j--， 但看到题解加了斜率优化后全是从11到NN顺着来的， 想问一下这是为什么，

回复

共 7 条回复，欢迎继续交流。

正在加载回复...