求助区间dp
查看原帖
求助区间dp
555900
Zhangvv_official楼主2023/6/29 11:36

思路与题解略有不同

设 fi,jf_{i,j} 为取 [i,j][i,j] 成绩单成本最小值

枚举 i,j,k,li,j,k,l 其中 i≤k≤l≤ji\leq k\leq l\leq j ,来求取走 [k,l][k,l] 再把 [i,k),(l,j][i,k),(l,j] 合并为一摞发放的成本最小值。或者自己单独成为一大摞。使用 ST表 求最值,时间复杂度 O(n4)O(n^4).

这个思路有没有问题?如果有问题错在哪里?我大号(禁言)写了个 40pts40pts 的代码

2023/6/29 11:36
加载中...