menu zcmimi's blog

arrow_back 斜率优化

f_i为前i个任务的费用,t_i为前i个任务时间的总和,w_i为前i个任务费用的总和

$$ fi=\min{j=0}^{i-1}(f_j+s\times(w_n-w_j

zc
2019-12-21 19:47

f_i表示前i块土地

f_i=\min_{j=1}^{i-1}(f_j+maxw[j-1][i]\times maxh[j-1][i])

这样的话怎么想都没有办法优化

我们

zc
2019-12-21 19:47

斜率优化入门题

f_i表示前i件玩具的制作费用

f_i=\min_{j=1}^{i-1}(f[j]+(i-j-1+s_i-s_j-L)^2)

显然\Theta(n^2)

zc
2019-12-21 19:47

f_i表示前i个拆分后最大战斗力和

f_i=\max_{j=1}^{i-1}(f_j+a(s_i-s_j)^2+b(s_i-s_j)+c)

这个很明显是斜率优化式子

zcmimi
2019-12-21 19:47

f(i,k)表示将前i个分k次的分数

我们可以dpk次就可以了

f_i为前i个,g_i为上一次dp的结果

$$ fi=\max{j=1}^{i-1}(g_j+

zc
2019-12-21 19:47

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __inline__ 
zc
2019-12-21 19:47

f_i为前i个任务的费用,t_i为前i个任务时间的总和,w_i为前i个任务费用的总和

$$ fi=\min{j=0}^{i-1}(f_j+s\times(w_n-w_j

zc
2019-12-21 19:47
1 / 1
Search
search