优质做网站价格,开个公司做购物网站,织梦禁止网站右击,课件模板Description
给你一个整数数组#xff0c;请你在其中选取若干个元素#xff0c;
使得其和值能被 k 整除#xff0c;输出和值最大的那个和值。
最后的数字可能很大#xff0c;所以结果需要对 19260817 取模。
Input
第一行是两个正整数 n#xff0c;k#xff1a;表示数…Description
给你一个整数数组请你在其中选取若干个元素
使得其和值能被 k 整除输出和值最大的那个和值。
最后的数字可能很大所以结果需要对 19260817 取模。
Input
第一行是两个正整数 nk表示数组的长度以及被整除的除数 k。
接下来是 n 行每行是一个正整数 num_i表示数组中第 i 个数。
n 10^5, k 100, num_i 10^9。
Output
能被 k 整除的元素最大和。
Sample Input
5 3
3
5
1
8
6
Sample Output
18
思路
将n个数取余分到0-k-1数组内然后dpdp[i][j]代表前0-i内的数相加余数为j的最大值。
#define _CRT_SECURE_NO_WARNINGS #includeiostream #includestring #includecstring #includecmath #includectime #includealgorithm #includeutility #includestack #includequeue #includevector #includeset #includemath.h #includemap #includeunordered_map using namespace std; typedef long long LL; typedef unsigned long long ULL; const int N 1000; LL dp[110][110]; vectorLL 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 p[0].size(); 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; }
