P3415. 通过软盘拷贝文件

解题思路

我们需要在 N 个文件 中挑选出若干个文件，使得总文件大小尽可能地大，因此本题属于一个典型的 背包问题。

但本题中存在一个 坑：文件必须按照 块 进行储存，且一个块只能储存一个文件。块的大小是 512。

假设此时要储存一个大小为 513 的文件，就必须使用 2 个块 来储存，且由于第二个块即使没有填满也不能再用于其他文件的存储，故占用的空间为 1024。

由于软盘总容量为 1474560 字节，一共包含 1474560 // 512 = 2880 个块，而每一个文件所占用的块数，也可以很方便地通过 ceil(file_i / 512) 得到，故我们可以将问题进行转化为如下描述：

对于已知容量为 2880 的背包，我们知道每一个文件所占空间 ceil(file_i / 512) 和价值 file_i，我们如何进行选择使得背包的总价值尽可能地大。

这就将题干描述的复杂情况，转化为了一个相对容易解决的 路径无关、求和最大值 的 01背包问题 了。其解法类似于 【DP】2023A-工作安排。

思路展开 本题的关键一步是换算单位：软盘按块分配空间，每块 512 字节，且一个块不能被两个文件共用，所以一个大小为 value 字节的文件实际占掉的是向上取整的 value/512 个块，代码用整数技巧 (value + 511) / 512 完成向上取整。软盘总容量 1474560 字节恰好等于 2880 个块，于是问题转化为标准 01 背包：背包容量是 m = 2880 个块，每个文件的重量是它占用的块数 spaceList[i]，价值是它的实际字节数 valueList[i]，目标是让装入软盘的文件字节总和最大。dp[i][j] 表示在前 i 个文件中挑选、占用不超过 j 个块时能保存的最大字节数。转移分两支：当前文件需要的块数超过 j 时只能不选，dp[i][j] = dp[i-1][j]；否则在不选与选（dp[i-1][j - space] + value）之间取较大值。要特别注意重量用的是块数、价值用的是字节数，两者不能混用——这正是本题与普通背包模板的差别所在。最终答案是 dp[n][m]，即用满 2880 个块的预算能保存的最大字节数。 复杂度分析 设 n 为文件数目，m 为软盘的总块数（固定为 2880）。

• 时间复杂度：O(n × m)，即约 2880n。主体是文件 × 容量的双重循环，每个状态只做常数次比较与取最大值。
• 空间复杂度：O(n × m)，用于二维 dp 表。由于每一行只依赖上一行，可压缩为一维数组并倒序遍历容量，把空间降到 O(m)。