题目描述
难度分:1031
输入n(1≤n≤100),k(1≤k≤n),d(1≤d≤100)和长为n的数组a(0≤a[i]≤109)。
从a中选出恰好k个数,满足元素和恰好是d的倍数。
输出元素和的最大值。如果无法得到d的倍数,输出−1。
输入样例1
4 2 2
1 2 3 4
输出样例1
6
输入样例2
3 1 2
1 3 5
输出样例2
-1
算法
动态规划
状态定义
f[i][mod][rest]表示当前考虑到第i个数,前i−1个数中已经选了k−rest个加起来模d等于mod的数,从i开始把后面的数选完能够选出来的最大和。在这个定义下,答案就应该是f[1][0][k]。
状态转移
如果rest<0或者i>n时没有满足mod=rest=0,则无解。否则当前的a[i]有选与不选两种决策,状态转移方程为f[i][mod][rest]=max(f[i+1][mod][rest],f[i+1][(mod+a[i])%d][rest−1]+a[i])。
复杂度分析
时间复杂度
状态数量是O(n3),单次转移是O(1),因此时间复杂度为O(n3)。
空间复杂度
空间消耗的瓶颈就在于DP
矩阵f,因此额外空间复杂度为O(n3)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 101;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, k, d, a[N];
LL f[N][N][N];
LL dfs(int i, int mod, int rest) {
if(rest < 0) return -INF;
if(i > n) return rest == 0 && mod == 0? 0: -INF;
LL &v = f[i][mod][rest];
if(v != -1) return v;
return v = max(dfs(i + 1, mod, rest), a[i] + dfs(i + 1, (mod + a[i]) % d, rest - 1));
}
int main() {
scanf("%d%d%d", &n, &k, &d);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
memset(f, -1, sizeof(f));
LL ans = max(-1LL, dfs(1, 0, k));
printf("%lld\n", ans);
return 0;
}