Codeforces Round #677 (Div. 3) F. Zero Remainder Sum (DP)

题意 ：给你一个$n\ast m$的矩阵，每行最多可以选择$\frac{m}{2}$个元素，将它们的权值加起来，问最后可以得到的最大的能被$k$整除的值是多少。
题解 ：用$dp[i][j]$来维护$1-i$行使余数为j时能取到的最大值，每次去更新一行前，先用$row[j][l][p]$来维护这一行到第$j$个元素时，在取了$l$个元素，余数为$p$的情况下能得到的最大值，再用$row[j][l][p]$来对$dp[i][j]$进行维护。注意每次维护都要判断前一状况是否合法，所以将$row$和$dp$都初始化为$-1$。

reply：一杯茶，一包烟，一道$dp$写一天。自己对于$dp$的题目都不是很了解，一直都靠队友写，所以写这道题目的时候很痛苦。最大的$bug$是用没有判断上一状态是否合法，同时进行状态转移的时候用当前的值来维护了当前状态，所以在维护$row$的时候会重复计算，最后自己写了个$l$先从大到小转移，再从小到大维护的版本。看了大佬的题解才知道了从$0$开始，维护下一状态。
换句话说，就是太菜了Orz。

#include <bits/stdc++.h>
using namespace std;#define endl "\n"typedef long long ll;const int maxn = 77;
int n, m, k;
int a[maxn][maxn], row[maxn][maxn][maxn], dp[maxn][maxn];void getRow(int i) {memset(row, - 1, sizeof(row));row[0][0][0] = 0;for (int j = 0; j < m; ++j) {for (int l = 0; l <= m / 2; ++l) {for (int p = 0; p < k; ++p) {if (row[j][l][p] >= 0) {row[j + 1][l][p] = max(row[j + 1][l][p], row[j][l][p]);if (l < m / 2) row[j + 1][l + 1][(p + a[i][j + 1]) % k] = max(row[j + 1][l + 1][(p + a[i][j + 1]) % k], row[j][l][p] + a[i][j + 1]);}}}}
}void solve() {memset(dp, -1, sizeof(dp));dp[0][0] = 0;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> a[i][j];}}for (int i = 1; i <= n; ++i) {getRow(i);for (int p = 0; p < k; ++p) {int tmp = -1;for (int l = 0; l <= m/2; ++l) {tmp = max(tmp, row[m][l][p]);}if (tmp < 0) continue;for (int pre = 0; pre < k; ++pre) {if (dp[i - 1][pre] < 0) continue;dp[i][(pre + p) % k] = max(dp[i][(pre + p) % k], dp[i - 1][pre] + tmp);}}}cout << dp[n][0] << endl;
}int _T;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> n >> m >> k;solve();
}