OI 牛客网 货物分组 – 题解 是的,又是一道考试时想出正解没有打出来的题目 货物分组 – 牛客网 根据题意,我们很容易想到一个朴素的类区间DP——令dp(i,j)dp(i, j)dp(i,j)表示现在将第iii件货物划分到第jjj箱中,且作为箱内的最后一件货物,所需最小花费。容易写出转移:dp(i,j)=mink∈[0,i)∧∑p=k+1iap≤Wdp(k,j−1)+∑p=k+1iap+极差{at∣t∈[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(i,j)=k∈[0,i)∧p=k+1∑iap≤Wmindp(k,j−1)+p=k+1∑iap+极差{at∣t∈[k+1,i]},初值有dp(0,0)=0dp(0, 0) = 0dp(0,0)=0,应求得minj∈[1,n]dp(n,j)\min\limits_{j \in [1, n]} dp(n, j)j∈[1,n]mindp(n,j)。 (更多…) More 2021年10月22日