待会儿来调,要不看看这个?
```cpp
f[i]表示打包前i件物品的最小费用
n=5, G=4
i= 1, 2, 3, 4, 5
w[i]= 3, 4, 2, 1, 4
f[i]= 1, 1, 5, 1, 1
f[i]=min{f[j]+cost(j+1,i)}
f[i]=min{f[j]+(s[i]-s[j]+i-j-1-G)^2}
令 t[i]=s[i]+i
令 H=G+1
f[i]=min{f[j]+(t[i]-t[j]-H)^2}
f[i]=min{f[j]+t[j]*t[j]+2*H*t[j]-2*t[j]*t[i]}
+t[i]*t[i]+H*H-2*t[i]*H
j号直线:y=f[j]+t[j]*t[j]+2*H*t[j]-2*t[j]*x
计算f[i]时取点横坐标t[i], 递增
i号直线:y=f[i]+t[i]*t[i]+2*H*t[i]-2*t[i]*x
截距b=f[i]+t[i]*t[i]+2*H*t[i] 递增
斜率k=-2*t[i] 递减
```
by wtcqwq @ 2022-07-27 10:32:08
@[World_Trade_Center](/user/241867) 我柿子按照第一篇题解化的(),把 $H$ 和 $t_j$ 看做整体。
by shyr @ 2022-07-27 10:37:44
破案了,预处理 $b_i$ 的那个循环要从 $0$ 开始。
by shyr @ 2022-07-27 10:43:35