求 k 整除最大元素和(dp)

Description

给你一个整数数组，请你在其中选取若干个元素，
使得其和值能被 k 整除，输出和值最大的那个和值。
最后的数字可能很大，所以结果需要对 19260817 取模。

Input

第一行是两个正整数 n，k：表示数组的长度，以及被整除的除数 k。
接下来是 n 行，每行是一个正整数 num_i，表示数组中第 i 个数。
n <= 10^5,  k <= 100, num_i <= 10^9。

Output

能被 k 整除的元素最大和。

Sample Input

Sample Output

思路：

将n个数取余分到0-（k-1）数组内，然后dp，dp[i][j]代表前0-i内的数相加，余数为j的最大值。

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include<ctime>
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1000;
LL dp[110][110];
vector p[110];
LL n,k,x;
bool cmp(LL x, LL y)
{
   return x > y;
}
int main() {
   cin >> n >> k;
   for (int i = 1; i <= n; i++)
   {
       scanf("%lld", &x);
       p[x % k].push_back(x);
   }
   for (int i = 0; i <= k-1; i++)
   sort(p[i].begin(), p[i].end(), cmp);
   x = 0;
   for (int i = 0; i        x += p[0][i];
   dp[0][0] = x;
   for (int i = 1; i <= k - 1; i++)
   {
       LL sum = 0;
       for (int j = 0; j < p[i].size(); j++)
       {
           sum += p[i][j];
           x = (j + 1) * i % k;
           for (int w = 0; w <= k - 1; w++)
           {
               if (j == 0) dp[i][w] = max(dp[i - 1][w], dp[i][w]);
               if (dp[i - 1][w])
                   dp[i][(x + w) % k] = max(dp[i][(x + w) % k], dp[i - 1][w] + sum);
           }
       }
   }
   cout << dp[k-1][0] % 19260817 << endl;
   return 0;
}

相关阅读:
【c#】反射
oracle学习48-oracle命令窗口执行sql语句
PyTorch、TensorFlow和Jax构建神经网络模型的标准化流程
荧光标记多肽FITC/AMC/FAM/Rhodamine/TAMRA/Cy3/Cy5/Cy7-Peptide
【光学】Matlab实现色散曲线拟合
InsCode Stable Diffusion 美图活动一期——即刻体验！来自 CSDN 的 SD 模型
11.18-创建视图 11.19-SELECT语法结构 11.20-简单查询 11.21-连接查询 11.22-聚集函数 11.23-授权语句
HTML代码中引入CSS样式的三种方式
力扣每日一题59：螺旋矩阵||
HTML中已经过时的标签

原文地址：https://blog.csdn.net/yusen_123/article/details/133978221