Zero Remainder Sum

  采用辅助数组 $ ndp[m + 1][\frac{m}{2}][k] $ 来求出每一行中在当前第 $ i $ 列，取了 $ j $ 个物品，总和模 $ k $ 的余数是 $ t $ 的最大和是多少。用 $ dp[n + 1][k] $ 来转移每一行的状态。

  #include <bits/stdc++.h>

  using namespace std;

  const int inf = std::numeric_limits<int>::max() / 2;

  signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::vector<int>> a(n, std::vector<int>(m));

    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) std::cin >> a[i][j];
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(k, -inf));
    
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
      std::vector<std::vector<std::vector<int>>> ndp(m + 1, std::vector<std::vector<int>>(m / 2 + 1, std::vector<int>(k, -inf)));
      ndp[0][0][0] = 0;
      for (int j = 0; j < m; j++) {
        ndp[j + 1] = ndp[j];
        for (int p = 0; p < m / 2; p++) {
          for (int q = 0; q < k; q++) {
            ndp[j + 1][p + 1][(q + a[i][j]) % k] = std::max(ndp[j + 1][p + 1][(q + a[i][j]) % k], ndp[j][p][q] + a[i][j]);
          }
        }
      }

      std::vector<int> Max(k, -inf);
      for (int j = 0; j < k; j++) {
        for (int p = 0; p <= m / 2; p++) {
          Max[j] = std::max(Max[j], ndp[m][p][j]);
        }
      }

      for (int j = 0; j < k; j++) {
        for (int p = 0; p < k; p++) {
          dp[i + 1][(j + p) % k] = std::max(dp[i + 1][(j + p) % k], dp[i][j] + Max[p]);
        }
      }
    }

    std::cout << dp[n][0] << "\n";

  }