有n个人,排成一列,每个人有着自己的耐心值$a[i]$,对于每个人来说,他的快乐值等于$a[i]*(j-1)$,j为他是第几个排完队的.你可以用一个类似于栈的东西来控制他们的顺序,让一部分人进去,然后逆序出来.求最小的快乐值.
菜鸡的我,看到这题完全没思路,看完题解写的.
应该是我目前做过的区间dp最难的题了.其实也没做多少题.
对于一个区间$[ij]$来说,我们要想使他最优,那就需要他们的顺序是最优的.
我们可以枚举这个i插入到的位置.
那么对于k这个点来说,因为他的位置为k,原来的位置是i,就相当于是往后面移动了$k-i$位.
对于区间$[k+1j]$来说,就是相当于后移了$k-i+1$位(因为前面有个i),需要加上前面的.
得到区间$[ij]$的最优解,那么一步步从最小区间$[ii+1]$开始推,这时候只需要考虑谁先谁后即可.