对于一个正整数x,定义x的“精神值”为小于x的所有x的约数之和。现在请你选出若干个不重复的正整数,这些正整数的和不超过s,使得他们的精神值之和最大。c++代码
时间: 2024-01-22 19:18:58 浏览: 185
很高兴回答您的问题!以下是我提供的 C 代码:
```c
#include <stdio.h>
#include <stdlib.h>
int main() {
int x, s;
scanf("%d %d", &x, &s);
int div_sum[x];
for (int i = 1; i <= x; i++) {
div_sum[i - 1] = 1; // 自己是它的约数
for (int j = 2; j * j <= i; j++) {
if (i % j == 0) {
div_sum[i - 1] += j; // 一对约数
if (j != i / j) {
div_sum[i - 1] += i / j;
}
}
}
}
int dp[x + 1][s + 1];
for (int i = 0; i <= x; i++) {
for (int j = 0; j <= s; j++) {
dp[i][j] = 0;
}
}
for (int i = 1; i <= x; i++) {
for (int j = s; j >= i; j--) {
dp[i][j] = dp[i - 1][j];
for (int k = 0; k * i <= j; k++) {
dp[i][j] = dp[i][j] > dp[i - 1][j - k * i] + k * div_sum[i - 1] ? dp[i][j] : dp[i - 1][j - k * i] + k * div_sum[i - 1];
}
}
}
printf("%d", dp[x][s]);
return 0;
}
```
这段代码使用了动态规划来解决这个问题。我们首先计算出所有小于等于 x 的数的约数之和,保存在 div_sum 数组中。然后,我们使用一个二维数组 dp[i][j] 来记录选取前 i 个数使得它们的和不超过 j 时的最大精神值。状态转移方程为:
- dp[i][j] = max(dp[i][j], dp[i - 1][j - k * i] + k * div_sum[i - 1])
其中 k 表示选取 i 的个数。最后,dp[x][s] 即为我们所求的答案。
阅读全文