F. Zero Remainder Sum - 题解

比赛与标签

比赛: Codeforces Round 677 (Div. 3) 标签: dp 难度: *2100

题目大意喵~

主人你好呀~ 这道题是这样的喵：

我们有一个 n x m 的数字矩阵，还有一个整数 k。我们的任务是从每一行里挑选一些数字，但有一个小小的限制哦：每一行最多只能挑选 ⌊m/2⌋ 个数字（也就是 m 除以 2 向下取整个数）。

我们的目标是，让我们挑选出的所有数字的总和，在能被 k 整除的前提下，尽可能地大！如果一个数都不能选，那总和就是 0 啦。最后，把这个最大的、能被 k 整除的总和打印出来就可以啦，喵~

简单来说就是：

输入: n, m, k 和一个 n x m 的矩阵。
要求:
1. 每行最多选 m/2 个数。
2. 所有选出的数的总和要能被 k 整除。
3. 在这个条件下，让这个总和最大。
输出: 这个最大的总和。

解题思路的说~

这道题看起来有点复杂，因为它既有行的约束，又有列的选择，还有一个全局的总和约束。但是不要怕，猫娘来帮你分析一下，你就会发现它的思路其实很清晰的喵！

问题的核心在于，我们在每一行的选择是相互独立的！也就是说，我在第一行选了哪些数，并不会影响我在第二行能选哪些数。这就像是给我们 n 个独立的包裹，我们要在每个包裹里按规则拿一些物品，最后组合起来满足全局条件。这种结构最适合用动态规划 (DP) 来解决啦，而且是分阶段的 DP 哦！

我们可以把整个问题分解成两个步骤：

第一步：处理每一行（行内 DP）

对于单独的一行，我们需要解决一个子问题：从这一行的 m 个数中，挑选 c 个数（c <= m/2），使得它们的和模 k 的余数是 r，并且这个和要最大。

这不就是一个经典的背包问题嘛！我们可以定义一个 DP 状态： dp[j][count][rem] 表示：考虑当前行的前 j 个数，已经挑选了 count 个数，它们的和模 k 的余数是 rem 时，能得到的最大和是多少。

状态转移就好办啦：对于第 j 个数 a[i][j]，我们有两种选择：

不选它：那状态就从前 j-1 个数继承过来。
选它：那就要从前 j-1 个数中选了 count-1 个数的状态转移过来。

不过，我们可以优化一下空间，把 j 这一维滚动掉。我们定义 row_dp[count][rem] 表示在当前行已经考虑过的元素中，选了 count 个，和的余数为 rem 的最大和。

当我们遍历到当前行的第 j 个元素 a[i][j] 时，我们用它来更新 row_dp 表。为了防止一个元素被重复计算，我们需要从后往前更新 count，就像 0-1 背包那样。

处理完一行所有的 m 个元素后，row_dp 表里就存满了这一行所有可能的选择方案（在满足每行最多选 m/2 个的限制下）所对应的最大和与余数。

第二步：合并所有行的结果（全局 DP）

当我们为每一行都计算出了 “选择任意 c (<= m/2) 个数，得到余数 r 的最大和” 之后，我们就要把这些行的结果合并起来啦！

这又是一个 DP 过程！我们可以定义一个新的 DP 状态： global_dp[rem] 表示：考虑完前面所有行之后，得到的总和模 k 余 rem 的最大值。

当我们处理完第 i 行，得到了该行的最优解集合 row_best[rem]（即在第 i 行选择不多于 m/2 个数，和模 k 余 rem 的最大值）后，我们就可以用它来更新 global_dp。

更新逻辑如下： new_global_dp[(r_old + r_row) % k] = max(new_global_dp[(r_old + r_row) % k], global_dp[r_old] + row_best[r_row])

这里 r_old 是之前行的总余数，r_row 是当前行贡献的余数。我们遍历所有可能的 r_old 和 r_row 组合，来更新合并后的 new_global_dp。

等所有 n 行都处理完后，global_dp[0] 就是我们最终的答案啦！因为它代表了总和模 k 余 0 的最大值，这不就是我们想要的嘛？

总结一下就是两层 DP：

内层 DP：对每一行做背包，求出该行不同余数下的最大和。
外层 DP：逐行合并结果，最终得到全局最优解。

是不是感觉清晰多啦？喵~

代码实现的喵~

下面是AC代码，猫娘已经帮你加上了详细的注释，让你更容易看懂每一步在做什么哦！

cpp

#include <iostream>
#include <vector>
#include <climits> // 为了使用 INT_MIN，不过这里用自定义的 INF 也可以

using namespace std;

// 定义一个非常小的数作为无穷大，用于初始化DP数组，表示该状态不可达
const int INF = -1000000000;

int main() {
    // 加快输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    cin >> n >> m >> k; // 读取行数、列数和除数k

    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    // 每行最多能选的元素数量
    int max_pick = m / 2;

    // 全局DP数组，global_dp[r] 表示已处理行的总和模k余r时的最大和
    vector<int> global_dp(k, INF);
    global_dp[0] = 0; // 初始状态：还没选任何数，总和是0，余数是0

    // --- 外层循环：逐行处理 ---
    for (int i = 0; i < n; i++) {
        // --- 内层DP：处理当前第 i 行 ---
        // row_dp[count][r] 表示在当前行选了 count 个数，和模k余r的最大和
        vector<vector<int>> row_dp(max_pick + 1, vector<int>(k, INF));
        row_dp[0][0] = 0; // 初始状态：不选任何数，和是0，余数是0

        // 遍历当前行的每个元素
        for (int j = 0; j < m; j++) {
            vector<vector<int>> next_dp = row_dp; // 创建一个临时DP表来存放本次更新的结果
            // 遍历所有可能的已选数量（从0到max_pick-1）
            for (int count = 0; count < max_pick; count++) {
                // 遍历所有可能的余数
                for (int r = 0; r < k; r++) {
                    if (row_dp[count][r] == INF) continue; // 如果这个状态不可达，就跳过

                    // 决策：选择当前元素 a[i][j]
                    int new_count = count + 1;
                    int new_r = (r + a[i][j]) % k;
                    int new_sum = row_dp[count][r] + a[i][j];

                    // 更新临时DP表
                    if (new_sum > next_dp[new_count][new_r]) {
                        next_dp[new_count][new_r] = new_sum;
                    }
                }
            }
            row_dp = next_dp; // 用更新后的结果覆盖原来的DP表
        }

        // --- 合并当前行的结果到全局DP ---
        // row_best[r] 存储当前行能得到的、和模k余r的最大和（不关心具体选了几个）
        vector<int> row_best(k, INF);
        for (int count = 0; count <= max_pick; count++) {
            for (int r = 0; r < k; r++) {
                if (row_dp[count][r] > row_best[r]) {
                    row_best[r] = row_dp[count][r];
                }
            }
        }

        // new_global 用于存储本次合并后的全局DP结果
        vector<int> new_global(k, INF);
        // 遍历之前所有行的余数 r_old
        for (int r_old = 0; r_old < k; r_old++) {
            if (global_dp[r_old] == INF) continue;
            // 遍历当前行的余数 r_row
            for (int r_row = 0; r_row < k; r_row++) {
                if (row_best[r_row] == INF) continue;

                // 计算新的总余数和总和
                int r_new = (r_old + r_row) % k;
                int total = global_dp[r_old] + row_best[r_row];

                // 更新 new_global
                if (total > new_global[r_new]) {
                    new_global[r_new] = total;
                }
            }
        }
        global_dp = new_global; // 更新全局DP表，为下一行做准备
    }

    // 所有行处理完毕，global_dp[0] 就是最终答案！
    // 如果没有任何合法的选择能使和大于0，结果可能还是0，所以要判断一下
    cout << max(0, global_dp[0]) << endl;

    return 0;
}

复杂度分析的说

时间复杂度: O(n * (m * (m/2) * k + k*k)) 的说。
- 我们有一个处理 n 行的大循环。
- 在每一行内部，我们要做一次行内 DP。这个 DP 过程需要遍历 m 个元素，对于每个元素，要更新一个大小为 (m/2) x k 的 DP 表，所以是 O(m * (m/2) * k)。
- 之后，我们合并行结果和全局结果，这需要两个 k 的循环，所以是 O(k*k)。
- 综合起来，总时间复杂度就是 O(n * (m^2 * k + k^2))。对于 n, m, k <= 70 的数据范围，这是完全可以接受的！
空间复杂度: O(m * k) 的说。
- global_dp 数组需要 O(k) 的空间。
- 在处理每一行时，我们需要 row_dp 和 next_dp 数组，它们的大小都是 O((m/2) * k)，也就是 O(m*k)。这是空间占用的主要部分。
- 所以总空间复杂度是 O(m*k)。

知识点与总结喵~

这道题真是一道非常棒的 DP 练习题呢！它教会了我们如何处理多阶段、多约束的组合优化问题。

分治思想: 核心是把一个大问题分解成 n 个独立的子问题（处理每一行），然后再把子问题的解合并起来。这是解决复杂问题时非常有用的思想。
分组背包模型: 这个问题可以看作一个分组背包的变种。每一行是一个“物品组”，在每个组里我们有多种选择（不同的余数对应不同的价值/和），我们的目标是在每个组里选一个“物品”（即一种余数方案），使得总价值最大且满足特定条件（总余数为0）。
DP状态设计: 状态设计是 DP 的灵魂！这道题的状态需要同时记录已选数量（为了满足 m/2 的限制）和当前和的余数（为了满足最终被 k 整除的限制），这是解题的关键。
初始化: 对于求最大值的 DP 问题，一定要把初始状态（除了起点）设置为一个极小值（比如负无穷），这样才能保证无效状态不会干扰到有效状态的转移。

希望这篇题解能帮到你，喵~ 如果还有不懂的地方，随时可以再来问猫娘哦！加油，你一定可以的！(ฅ'ω'ฅ)

F. Zero Remainder Sum - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路的说~ ​

代码实现的喵~ ​

复杂度分析的说 ​

知识点与总结喵~ ​