![uoj#246. 【UER #7】套路（dp+分块？分类讨论？）然而我们全然不用枚举这个kf[i]=min(f[i],f[i-1])](/uploads/reation/bcimg14.png)
uoj#246. 【UER #7】套路（dp+分块？分类讨论？）然而我们全然不用枚举这个kf[i]=min(f[i],f[i-1])
题目链接分析： 目前为止我只能理解dp部分我就喜欢这种单纯不做作的题目 一看名字就明白了这道题的本质中二的题目描述很显然，我们的关键就是求出最小相似度 朴素算法n^4如果我们现在有一个权值数组 显然，每一个数只可能与最邻近ta的数产生贡献 假设我们要求[i,j]之间的最小差距 那我们可以分成两部分[i,k],[k+1,j] 枚举k，取最小就可以了但是这样的复杂度是n^3然而我们全然不用
