【题目描述】

众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。数据保证一定有解。

【输入格式】
从标准输入读入数据。

第一行包括 2 个正整数 n, K。
第二行 n 个正整数，代表给定的 n 个数。

【输出格式】
输出到标准输出。
输出一行一个整数代表所求的和。

【样例入】
4 3
1 2 3 4

【样例输出】
9

【样例解释】
选择2、3、4。

【数据约定】
对于 30% 的数据，n <= 100。
对于 60% 的数据，n <= 1000。
对于另外 20% 的数据，K <= 10。
对于 100% 的数据，1 <= n <= 10^5, 1 <= K <= 10^3，给定的 n 个数均不超过 10^8。

解题思路：

暴力O(n^3),只能拿一部分的分

dp：一个状态是合法的，它肯定是由另一个合法状态转化过来的

决策过程和背包问题(n件物品，w[i]和v[i]，选择w[i]之和不超过M，且v[i]之和最大)类似，但有些需要注意的点

将v[i]%k作为w[i]，(a+b+c)%k==0等价于（a%k+b%k+c%k）%k==0

状态转移方程：

dp[j+1][(t+w[i])%k]=max(dp[j][t]+v[i],dp[j+1][(t+w[i])%k])  选第i个和不选第i个 (j==0&&t==0)||dp[j][t]

注意：j的遍历从2～0，且放在t循环的外面一层！！

ac代码：

#include <iostream>
#include <cmath>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#define maxn 100005
using namespace std;
int n,k;
int dp[5][1005]={0},w[maxn],v[maxn];
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        w[i]=v[i]%k;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=2;j>=0;j--)
        {
            for(int t=k-1;t>=0;t--)
            {
                if((j==0&&t==0)||dp[j][t])//选了0个和模k为0 or 已经选好了j个和模k为t，更新选j+1个时dp值
                    dp[j+1][(t+w[i])%k]=max(dp[j][t]+v[i],dp[j+1][(t+w[i])%k]);//选v[i]和不选v[i]
            }
        }
    }
    cout<<dp[3][0]<<endl;
    return 0;
}

测试样例：

11 3
1 3 6 2 5 7 4 49 21 43 21

输出：99