题意:nxm的矩阵, 每一行最多可以选m/2个, 求选出所有值的和能被k整除的最大值;
分别算每一行余数的最大值,然后枚举计算前n行最大值
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
int n, m, k;
int main()
{while(cin >> n >> m >> k){vector<vector<int>> a(n + 1, vector<int>(m + 1));for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)cin >> a[i][j];vector<vector<int>>dp(n+1, vector<int>(k, -INF));for(int i = 1; i <= n; ++i){vector<vector<int>>tmp(m + 1, vector<int>(k, -INF));tmp[0][0] = 0;for(int j = 1; j <= m; ++j){for(int d = min(j, m / 2); d >= 1; --d){for(int z = 0; z < k; ++z)tmp[d][(z + a[i][j]) % k] = max(tmp[d][(z + a[i][j]) % k], tmp[d-1][z] + a[i][j]);}}for(int k1 = 0; k1 < k; ++k1){for(int d = 0; d <= m / 2; ++d){dp[i][k1] = max(dp[i][k1], tmp[d][k1]);}}}vector<vector<int>> res(n+1, vector<int>(k, -INF));res[0][0] = 0;for(int i = 1; i <= n; ++i){for(int k1 = 0; k1 < k; ++k1)for(int k2 = 0; k2 < k; ++k2){res[i][(k1 + k2) % k] = max(res[i-1][k1] + dp[i][k2], res[i][(k1 + k2) % k]);}}cout << res[n][0] << endl;}
}