保存帖子
发现
索引
热门
陶片放逐
关于
求助:对这题斜率优化后的滚动数组有点疑惑
板块
P3648 [APIO2014] 序列分割
楼主
190040257a
当前回复
7
已保存回复
7
发布时间
2020/8/19 15:32
上次更新
2023/11/6 19:56:09
查看原帖
更新帖子
被骇客
银
狼
阻止的越权访问
保存失败
求助:对这题斜率优化后的滚动数组有点疑惑
190040257a
楼主
2020/8/19 15:32
这题状态转移方程是
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
−
1
]
[
k
]
+
(
s
u
m
[
j
]
−
s
u
m
[
k
]
)
∗
s
u
m
[
k
]
)
f[ i][j]=max(f[i-1][k]+(sum[j]-sum[k])*sum[k])
f
[
i
]
[
j
]
=
ma
x
(
f
[
i
−
1
]
[
k
]
+
(
s
u
m
[
j
]
−
s
u
m
[
k
])
∗
s
u
m
[
k
])
sum为前缀和嘛,按理说把第一维压掉后应该跟01背包一样,
j
j
j
从
N
N
N
到
1
1
1
,
j
−
−
j--
j
−
−
, 但看到题解加了斜率优化后全是从
1
1
1
到
N
N
N
顺着来的, 想问一下这是为什么,
2020/8/19 15:32
加载中...