题解：CF1433F Zero Remainder Sum
a_small_penguin
·
·
题解
这道题和 AT_abc248_c 十分类似，于是蒟蒻在这道题的基础上改动了一点，通过了此题。
对于 AT_abc248_c 这道题，设计 dp 状态如下：
考虑转移：（假设该选 $a_x$）
$$
f_{i,j} = \begin{cases}
f_{i,j} & j = 0 \\
\max(f_{i, j}, f_{j - 1, (j - a_x) \bmod d}) & j \ne 0
\end{cases}
$$
那该如何将 [AT_abc248_c](https://atcoder.jp/contests/abc248/tasks/abc248_c?lang=en) 转化为这道题呢?
就是对于每一行跑一遍 dp，再把 $f_{0,j}$ 为下一次 dp 初始化为 $\min^{\left\lfloor\frac{m}{2}\right\rfloor}_{i = 1} f_{i,j}$。
答案就是 $f_{0,0}$。
code：
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, d;
int a[109];
long long f[109][109];
inline void dp(int k) {
for(int i = 1; i <= n; i++) {
for(int j = k; j >= 0; j--) {
for(int r = d - 1; r >= 0; r--) {
if(!j) f[j][r] = f[j][r];
else f[j][r] = max(f[j][r], f[j - 1][(r + d - a[i] % d) % d] + a[i]);
}
}
}
for(int i = 0; i < d; i++) {
for(int j = 0; j <= k; j ++) {
f[0][i] = max(f[0][i], f[j][i]);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> m >> n >> d;
memset(f, -0x7f, sizeof(f));
f[0][0] = 0;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
cin >> a[j];
}
dp(n / 2);
}
cout << f[0][0];
return 0;
}
```