CF1437C Chef Monocarp

题意

(n) 道菜品被放入了一个烤炉中,每个菜品都有一个最佳取出时间 (t_i) , 现在按一定顺序把菜品取出,每一个时刻只能取出至多一道菜品,每道菜的不美味度为 (|T-t_i|) , (T) 是取出这道菜的时刻,求把所有菜品都取出的最小不美味度?

(1 le n le 200)

(1le t_i le n)

思路

先将菜品按照 (t_i) 排序,则菜品是依次取出

f[i][j] 表示在 j 时刻取出第 i 道菜品的最小不美味度, (O(n)) 转移就可以

复杂度 (O(n^3))

看了别人的题解,好像可以直接 O(1) 转移

改一下状态定义,改成在 j 时刻已经取完了前 i 道菜品

f[i][j] = min(f[i][j-1], f[i-1][j-1] + |j - t[i]|)

更改一下状态定义的位置

f[i][j] = min(f[i-1][j], f[i-1][j-1] + |i - t[j]|)

可以倒序压一维

(O(n^2))

原文地址:https://www.cnblogs.com/sduwh/p/14313782.html