传智杯 第六届—第二场—D
题目描述:
小红拿到了一个数组，她想取一些数使得取的数之和尽可能大，但要求这个和必须是 k k\ k 的倍数。你能帮帮她吗？
输入描述:
第一行输入两个正整数 n 和 k 。第二行输入 n 个正整数 ai 。（1≤n,k≤10^3，1≤ai≤10^10）
输出描述:
如果没有合法方案，输出 -1；否则输出最大的和。
示例1
输入：
5 5
4 8 2 9 1输出：
20
说明：
取后四个数即可。
想法1：暴力方法
最终运行超时，由于循环次数过大。设置一个二维数组，每个一维数组代表在第i个正整数出现过后，会有的和的所有情况，相较于上次（即上个正整数），这次和的情况为上次的两倍，分别是在之前的情况下再分别加x和不加x的两种情况，并将这所有的情况都存储在该正整数所对应的数组中，再下次的情况又*2。所以最终的情况将是2^n，当n很大的时候，这个值将非常的大，所以会导致运行超时。其中第一个一维数组含有的数据个数为2（1*2），第二个一维数组含有的数据个数为4（2*2），第三个一维数组含有的数据个数为8（4*2）........第n个一维数组含有的数据个数为2^n（2^(n-1)*2）。
代码：
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
vector <long long>sum[1001]; //用于保存和
int main()
{
//输入
int n, k; //正整数个数，倍数
cin >> n >> k;
long long max = 0;
long long* a = new long long[n];
for (int i = 0;i < n;i++)
{
cin >> a[i];
if (i == 0)
{
sum[i].push_back(0);
sum[i].push_back(a[i]);
continue;
}
//记录下所有和的情况
for (int j = 0;j < pow(2, i);j++) //不加a[i]
{
sum[i].push_back(sum[i-1][j]);
if (sum[i][j] % k == 0) //可以被整除
{
max = max > sum[i][j] ? max : sum[i][j];
}
}
for (int j = 0;j < pow(2, i);j++) //加a[i]
{
sum[i].push_back(sum[i - 1][j] + a[i]);
if (sum[i][j + pow(2, i)] % k == 0) //可以被整除
{
max = max > sum[i][j] ? max : sum[i][j + pow(2, i)];
}
}
sum[i - 1].clear();
}
//输出
cout << (max != 0 ? max : -1)<<endl;
system("pause");
return 0;
}
想法2：优化
在想法1的基础上，能不能减少循环的次数进行优化。我们可以考虑将每个正整数所含的一维数组变成定量的，可以将每个一维数组设置成k个空间，即将每次的结果保留在以sum%k为下标的数组对应位置，即每次更新对应位置的值，以示例1为例，其二维数组的结果是：
其中n=5;k=5，则会分配5*5的二维数组，行为第i个正整数，列为取余为j
余0 余1 余2 余3 余4
+4 0 0 0 0 4
+8 0 0 12 8 4
+2 10 6 12 8 14
+9 15 21 17 23 19
+1 20 21 22 23 24将上一个一维数组的值+这次的正整数的值所得到的新值写到取余过后的正确位置，并将其与上次的值进行比较，取更大的值，并保存在数组中，直到最后一次计算结束，就可以得到取余为0的最大值。
代码：
#include<iostream>
using namespace std;
int main()
{
//输入
int n, k; //正整数个数，倍数
cin >> n >> k;
long long* a = new long long[n];
long long sum[1000][1000]; //用于保存
for (int i = 0;i < n;i++)
{
cin >> a[i];
if (i == 0)
{
sum[i][a[i] % k] = a[i];
continue;
}
for (int j = 0;j < k;j++) //不加x
{
sum[i][j] = sum[i - 1][j];
}
for (int j = 0;j < k;j++) //加x
{
sum[i][(a[i] + sum[i - 1][j]) % k] = max(a[i] + sum[i - 1][j], sum[i-1][(a[i] + sum[i - 1][j]) % k]);
}
}
//输出
cout << (sum[n - 1][0] != 0 ? sum[n - 1][0] : -1) << endl;
system("pause");
return 0;
}