[ABC400F] Happy Birthday! 3 题解
思量正难则反。标题转化为：一个环上有 n n n 个物品，颜色分别为 c o l i col_i coli，每次操纵选择两个数 i , j i, j i,j 使得 ∀ k ∈ [ i , j ] , c o l k = c o l i ∨ c o l k = 0 \forall k \in , col_k = col_i \lor col_k = 0 ∀k∈,colk=coli∨colk=0，将 [ i , j ] 中的每个物品的颜色都设为 0 0 0。（下文将这种操纵称为“漂白”。）一次操纵的代价为 j − i + 1 + x c o l i j - i + 1 + x_{col_i} j−i+1+xcoli。求将整个环漂白的最小总代价。
先断环为链。设 d p i , j dp_{i, j} dpi,j 表示将 [ i , j ] 漂白的最小代价，那么显然有 d p i , j = min k = i j − 1 d p i , k + d p k + 1 , j dp_{i, j} = \min_{k = i}^{j - 1} dp_{i, k} + dp_{k + 1, j} dpi,j=mink=ij−1dpi,k+dpk+1,j。
设 f i , j f_{i, j} fi,j 表示使 [ i , j ] 可以大概漂白的最小代价，那么显然有 f i , j = min k = 1 j − 1 f i , k + d p k + 1 , j f_{i, j} = \min_{k = 1}^{j - 1} f_{i, k} + dp_{k + 1, j} fi,j=mink=1j−1fi,k+dpk+1,j。当 c o l i = c o l j col_i = col_j coli=colj 时，有 f i , j = min ( f i , j , f i , j − 1 ) , d p i , j = min ( d p i , j , f i , j + j − i + x c o l i ) f_{i, j} = \min (f_{i, j}, f_{i, j - 1}), dp_{i, j} = \min (dp_{i, j}, f_{i, j} + j - i + x_{col_i}) fi,j=min(fi,j,fi,j−1),dpi,j=min(dpi,j,fi,j+j−i+xcoli)。
答案即为 min i = 1 n d p i , i + n − 1 \min_{i = 1}^n dp_{i, i + n - 1} mini=1ndpi,i+n−1。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]