求助:对这题斜率优化后的滚动数组有点疑惑
查看原帖
求助:对这题斜率优化后的滚动数组有点疑惑
233957
190040257a楼主2020/8/19 15:32

这题状态转移方程是

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

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

2020/8/19 15:32
加载中...