CodeForces Div3.F

CodeForces Div3.F - Zero Remainder Sum

题意

给定一个 (n imes m)的矩阵，你可以在每一行选择不多于(frac{n}{2})个元素，使得整体选择的元素的和模(k)为0，并且和越大越好。

[1leq n,m,kleq 70\ 1leq a_{ij} leq 70 ]

分析

据说是一道标准的动态规划问题。

令(dp[x][y][cnt][rem])表示当前在(i,j)，当前行已经选取了(cnt)个元素并且当前的余数是(rem)

初始化(dp)为负无穷，(dp[0][0][0][0] = 0)

状态转移

[dp[nx][ny][cnt][rem] = max(dp[nx][ny][cnt][rem],dp[x][y][cnt][rem]) 表示不取当前元素\ dp[nx][ny][cnt + 1][(rem+a_{ij})\%k] = max(dp[nx][ny][cnt+1][(rem+a_{ij})\%k],dp[x][y][cnt][rem] + a_{ij}) 表示取当前元素 ]

答案就是(max(dp[n][0][0][0],0))，这里可以认为是最后一行的下一行的第一个元素

注意一下实现的时候直接套上四个(for)就行了

代码

const int M = 70;

int a[M][M];
int dp[M][M][M][M];

int main() {
    int n = readint();
    int m = readint();
    int k = readint();
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            a[i][j] = readint();
    memset(dp, -INF, sizeof dp);
    dp[0][0][0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int cnt = 0; cnt < m / 2 + 1; cnt++) {
                for (int rem = 0; rem < k; rem++) {
                    if (dp[i][j][cnt][rem] == -INF) continue;
                    int nx = (j == m - 1 ? i + 1 : i);
                    int ny = (j == m - 1 ? 0 : j + 1);
                    if (i != nx)
                        dp[nx][ny][0][rem] = max(dp[nx][ny][0][rem], dp[i][j][cnt][rem]);
                    else
                        dp[nx][ny][cnt][rem] = max(dp[nx][ny][cnt][rem], dp[i][j][cnt][rem]);
                    if (cnt + 1 <= m / 2) {
                        int nrem = (rem + a[i][j]) % k;
                        if (i != nx)
                            dp[nx][ny][0][nrem] = max(dp[nx][ny][0][nrem], dp[i][j][cnt][rem] + a[i][j]);
                        else
                            dp[nx][ny][cnt + 1][nrem] = max(dp[nx][ny][cnt + 1][nrem], dp[i][j][cnt][rem] + a[i][j]);
                    }
                }
            }
        }
    }
    cout << max(0,dp[n][0][0][0]);
}