题目描述

N堆糖果，不同数目，求不同取法下，糖果的数目和mod k 余0，且和最大

(简单dp) $O(n^2)$

显然的背包问题，dp
分析前i个数据的满足条件的最大和，有两种情况：
1.不包含第i个数，即等于前i-1个数据的满足条件的最大和
2.含有第i个数，即等于第i个数temp+前i-1个数据的mod k余数为（-temp&k）的最大和
因为c++的mod的余数有负数，所以严谨写法为 (-temp&k+k)&k

因此，建立数据结构dp[i][j],表示前i个数，余数为j的最大和，由此dp[n][0]即为所求的前n个数中，余数为0的最大和

C++ 代码

#include <iostream>  
#include <algorithm>  
#include <cstdio> 
#include <string> 
using namespace std;
const int N = 110;
int dp[N][N];  //dp[i][j]表示前i个数中，最大的mod k 余 j的和
int main()
{
    int n, k;
    int temp;
    scanf("%d%d", &n, &k);
    memset(dp, -0x3f, sizeof dp);  //最小值为-0x3f  //memset要求头文件为string，或者用cstring不写iostream(c语言风格)
    dp[0][0] = 0;   //前0个数余数为0
    for ( int i = 1; i <= n; i++ ) {
        scanf("%d", &temp);
        for (int j = 0; j < k; j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j + k - temp % k) % k] + temp);
            //第一种情况：不包含第i个数，所以等于dp[i - 1][j]
            //第二种情况：含有第i个数，等于dp[i - 1][(j + k - temp % k) % k]+temp
            //(j + k - temp % k) % k 即是 (j-temp)%k,即加上temp后mod k等于j
        }
    }
    cout << dp[n][0];  //前n个数中，最大的mod k 余 0的和
    return 0;
}