Zero Remainder Sum

Zero Remainder Sum

链接
题意

给出n行，每行有m个，每行可选小于等于m/2个，使得和是k的倍数，且和最大

题解

开4维dp，第i行的第j列，拿的个数cnt，余数res_k

//注意边界

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <set>
using namespace std;
const int MAX = 80;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
typedef long long ll;
int a[MAX][MAX];
int dp[MAX][MAX][MAX][MAX];
int main() {
    int n, m, k;scanf("%d%d%d", &n, &m, &k);for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
    scanf("%d", &a[i][j]);}}memset(dp, -1, 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 + 1 <= m / 2 + 1; cnt++) {
    for(int res_k = 0; res_k < k; res_k++) {
    if(j != m - 1) {
    //不选更新最大值dp[i][j + 1][cnt][res_k] = max(dp[i][j + 1][cnt][res_k], dp[i][j][cnt][res_k]);//选的话，要保证dp之前更新过，即是有意义的if(cnt >= 0 && dp[i][j][cnt][res_k] != -1) {
    dp[i][j + 1][cnt + 1][(res_k + a[i][j]) % k] = max(dp[i][j][cnt][res_k] + a[i][j], dp[i][j + 1][cnt + 1][(res_k + a[i][j]) % k]);}}else {
    //每一行的最后一列要更新到下一行的第一个//且cnt也要要与同为cnt = 0比较dp[i + 1][0][0][res_k] = max(dp[i + 1][0][0][res_k], dp[i][j][cnt][res_k]);if(cnt >= 0 && dp[i][j][cnt][res_k] != -1 && cnt + 1 <= m / 2) {
     //原本过不了是cnt + 1 <= m / 2没加//为什么要加呢？因为无论是上面的cnt + 1 <= m / 2 + 1还是这个都是确保dp[i][j][cnt][res_k]是有意义的dp[i + 1][0][0][(res_k + a[i][j]) % k] = max(dp[i][j][cnt][res_k] + a[i][j], dp[i + 1][0][0][(res_k + a[i][j]) % k]);}}}}}}printf("%d\n", dp[n][0][0][0]);
}

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <set>
using namespace std;
// 第二遍打一边
const int MAX = 80;
int dp[MAX][MAX][MAX][MAX];
int a[MAX][MAX];int main() {
    int n, m, k;scanf("%d%d%d", &n, &m, &k);for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
    scanf("%d", &a[i][j]);}}memset(dp, -1, 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 + 1 <= m / 2 + 1; cnt++) {
    for(int res = 0; res < k; res++) {
    if(j != m - 1) {
    dp[i][j + 1][cnt][res] = max(dp[i][j + 1][cnt][res], dp[i][j][cnt][res]);if(dp[i][j][cnt][res] != -1) {
    dp[i][j + 1][cnt + 1][(res + a[i][j]) % k] = max(dp[i][j + 1][cnt + 1][(res + a[i][j]) % k], dp[i][j][cnt][res] + a[i][j]);}}else {
    dp[i + 1][0][0][res] = max(dp[i + 1][0][0][res], dp[i][j][cnt][res]);if(dp[i][j][cnt][res] != -1 && cnt + 1 <= m / 2) {
    // 选 --> cnt + 1 <= m / 2dp[i + 1][0][0][(res + a[i][j]) % k] = max(dp[i + 1][0][0][(res + a[i][j]) % k], dp[i][j][cnt][res] + a[i][j]);}}}}}}printf("%d\n", dp[n][0][0][0]);
}