题解

思路

若产品 $i$ 在买车前 $t$ 个月选择，那么买车时它的净贡献是

$$a_i-b_i\min(k_i,t).$$

选择 $s$ 个产品后无需空等月份：空等只会增加还款。因此这些产品分别占用 $t=0,1,\ldots,s-1$，问题也可以看成产品与月份位置的最大权匹配。

做法

子任务 1：枚举顺序

枚举所有产品排列的所有前缀，直接计算每个前缀在最后一个月月中的余额。复杂度为 $O(n!\,n^2)$。

子任务 2：匈牙利算法

建立二分图。左侧位置 $t$ 与右侧产品 $i$ 的权为 $a_i-b_i\min(k_i,t)$。依次加入位置 $0,1,\ldots$，每次匈牙利算法得到选择恰好当前数量产品时的最大权匹配，取所有匹配规模的最大值。复杂度为 $O(n^3)$。

满分算法

将产品按 $b_i$ 从大到小排序。对于一个最终被选择的产品：

• 若买车前已经完成全部还款，它的贡献固定为 $a_i-k_ib_i$；
• 否则，所有这类尚未还清的产品按 $b_i$ 递减排列最优。若它是其中第 $j$ 个，贡献为 $a_i-(j-1)b_i$。

设 $dp[i][j]$ 表示考虑排序后前 $i$ 个产品，其中有 $j$ 个被归入“买车时尚未还清”这一类时的最大贡献。产品 $i$ 有三种选择：不用；选用且已还清；选用且成为第 $j$ 个尚未还清产品。转移为

$$\begin{aligned} dp[i][j]&\gets dp[i-1][j],\\ dp[i][j]&\gets dp[i-1][j]+a_i-k_ib_i,\\ dp[i][j]&\gets dp[i-1][j-1]+a_i-(j-1)b_i. \end{aligned}$$

所有状态中的最大值即答案。

复杂度

枚举算法为 $O(n!\,n^2)$，匈牙利算法为 $O(n^3)$。满分动态规划为 $O(n^2)$ 时间、$O(n)$ 额外空间。