题目链接
题目大意
给定一个 \(N × M\) 的矩阵
对于矩阵的每一行，你可以在该行挑选不超过 \(⌊m/2⌋\) 个元素
要求挑选的所有元素的和为 \(K\) 的倍数，问可以挑选的最大元素和为多少
解题思路
先考虑如果题目给的是个一维数组而不是二维矩阵该怎么做 \(?\)
可以定义 \(dp[N][N][N][2]\) ，其含义为 \(↓\)
当前在第 \(j\) 个位置，已经选择了 \(k\) 个数 ，挑选的元素的和模完 \(K\) 之后的值为 \(L\)
\(0\) 表示元素 \(a[j]\) 不挑选 , \(1\) 表示元素 \(a[j]\) 挑选
那么不难得到转移方程
\(dp[j][k][l][0] = max(dp[j - 1][k][l][0] , dp[j - 1][k][l][1])\)
\(dp[j][k][(l + x)\%K][1] = max(dp[j - 1][k - 1][l][0] , dp[j - 1][k - 1][l][1]) + a[j]\)
而把一维延伸至二维只要在以上操作上再做一次竖向的 \(dp\) 即可
AC_Code
#include<bits/stdc++.h>
using namespace std;
const int N = 80;
int a[N][N] , ans[N][N] , dp[N][N][N][2];
signed main()
{
memset(ans , 128 , sizeof(ans)) , ans[0][0] = 0;
int n , m , K , res = 0;
cin >> n >> m >> K;
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 ++)
{
memset(dp , 128 , sizeof(dp));
for(int j = 0 ; j <= m ; j ++) dp[j][0][0][0] = 0;
for(int j = 1 ; j <= m ; j ++)
{
int x = a[i][j];
for(int l = 0 ; l < K ; l ++)
{
for(int k = 1 ; k <= m / 2 ; k ++)
{
int ha = max(dp[j - 1][k][l][0] , dp[j - 1][k][l][1]);
dp[j][k][l][0] = max(dp[j][k][l][0] , ha);
int he = -0x3f3f3f3f;
if(k) he = max(dp[j - 1][k - 1][l][0] , dp[j - 1][k - 1][l][1]) + a[i][j];
dp[j][k][(l + x) % K][1] = max(dp[j][k][(l + x) % K][1] , he);
}
}
}
for(int h = 0 ; h <= m / 2 ; h ++) for(int l = 0 ; l < K ; l ++) for(int L = 0 ; L < K ; L ++)
{
int x = max(max(dp[m][h][L][0] , dp[m][h][L][1]) , 0);
int y = ans[i][(l + x) % K];
ans[i][l] = max(ans[i][l] , ans[i - 1][l]);
ans[i][(l + x) % K] = max(max(y , ans[i - 1][(l + x) % K]) , ans[i - 1][l] + x);
}
}
res = max(res , ans[n][0]);
cout << res << '\n';
return 0;
}