题解 | 小红取数

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  正确的代码是看了别的题解菜想出来的，一开始我用的是贪心，这里主要讲讲为什么我的思路错了。主要的问题在于我只考虑了两个数相加的情况但是实际上可能会有如三个2相加变成3的倍数的这种情况
/*#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  long long ans = 0;
  int n, k, x;
  cin >> n >> k;
  vector<vector<int>> a(k, vector<int>());
  for (int i = 0; i < n; i++){
    cin >> x;
    a[x % k].push_back(x);
  }
  int i = 1, j = k - 1;
  for (int i = 0; i < k; i++)
    sort(a[i].begin(), a[i].end());
  while(i < j){
    if (a[i].size() && a[j].size()){
      ans += (a[i].back() + a[j].back());
      a[i].pop_back();
      a[j].pop_back();
    }
    else{
      i++;
      j--;
    }
  }
  if (i == j){
    while(a[i].size() >= 2){
      ans += a[i].back();
      a[i].pop_back();
      ans += a[i].back();
      a[i].pop_back();
    }
  }
  while(a[0].size()){
    ans+=a[0].back();
    a[0].pop_back();
  }
  if (ans == 0) ans = -1;
  cout << ans;
  return 0;
}
// 64 位输出请用 printf("%lld")*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main(){
  ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++){
    cin >> a[i];
  }
  vector<vector<long long>> ans(2 , vector<long long>(k, LONG_MIN));
  ans[0][0] = 0;
  for (int i = 0; i < n; i++){
    for (long long j = 0; j < k; j++){//-------------这里要注意j要开longlong不然会溢出导致下标越界
      ans[1][(j + a[i]) % k] = max(ans[0][(j + a[i]) % k], ans[0][j] + a[i]);
    }
    for (int j = 0; j < k; j++)
      ans[0][j] = ans[1][j];
  }
  if (ans[0][0] <= 0) cout << -1;
  else cout << ans[0][0];
  return 0;
}