CF1433F Zero Remainder Sum 题解

题意

给定正整数n, m, k(1 \leq n, m, k \leq 70)，接下来给定一个n \times m的矩阵，保证矩阵中每个数不大于70。请在矩阵每一行中取出不多于[{ \frac{m}{2} }]个数，使得所有行取出的数的总和恰好能被k整除。

题解

四维DP。记录在当前位置(i,j)，已经选取了cnt个数，以及之前所有选择的数的和除以k的余数即\mod k = remainder的最大值。注意处理行首行末的数即可。转移方程：

f[i][j+1][cnt][rem]=
max \lbrace f[i][j+1][cnt][rem], f[i][j][cnt][rem] \rbrace

f[i][j+1][cnt+1][(rem+A_{ij}) \% k]=
max
\begin{cases}
f[i][j+1][cnt+1][(rem+A_{ij}) \% k] \\
f[i][j][cnt][rem] + A_{ij}
\end{cases}

答案为f[n+1][0][0][0]。