极差

是的,又是一道考试时想出正解没有打出来的题目

货物分组 – 牛客网

根据题意,我们很容易想到一个朴素的类区间DP——令dp(i,j)dp(i, j)表示现在将第ii件货物划分到第jj箱中,且作为箱内的最后一件货物,所需最小花费。容易写出转移:dp(i,j)=mink[0,i)p=k+1iapWdp(k,j1)+p=k+1iap+极差{att[k+1,i]}dp(i, j) = \min\limits_{k \in [0, i) \land \sum\limits_{p=k+1}^{i} a_p \leq W } dp(k, j-1) + \sum\limits_{p=k+1}^{i} a_p + \textrm{极差}\{a_t \mid t \in [k + 1, i]\},初值有dp(0,0)=0dp(0, 0) = 0,应求得minj[1,n]dp(n,j)\min\limits_{j \in [1, n]} dp(n, j)

(更多…)

More
  • 2021年10月22日