A20980. 题解

代码懒的写了，就用 AI 生成的，在此致歉。

背包 dp。

首先我们观察题目，边界为 $[1,S]$ 是显然的，然后我们枚举所有 $i \in [1,S]$ 的 $σ(i)-i$ 作为第 $i$ 个物品的价值，$i$ 作为重量，$S$ 作为容量，接下来做正常背包 dp 即可。

代码中用 /* */ 代表作者自己写的代码介绍，// 代表 AI 代码注释。

代码中有防抄袭，提交无法通过。

#include <bits/stdc++.h>
using namespace std;

int main() {
   int S;
   cin >> S;
   /* 下面是枚举因数的部分 */
   // 预处理每个数的真因数之和（不含本身）
   vector<int> sum(S + 1, 0);
   
   // 枚举因数 d
   for (int d = 1; d <= S; d++) {
       // 将 d 加到它的倍数上（从 2*d 开始，因为不含本身）
       for (int m = 2 * d; m <= S; m += d) {
           sum[m] += d;
       }
   }
   /* 下面是背包 dp 模板 */
   // 0/1 背包
   vecotr<int> dp(S + 1, 0);
   for (int i = 1; i <= S; i++) {        // 物品：数字 i
       for (int j = S; j >= i; j--) {    // 容量从大到小 /* 从大到小是因为如果从小到大数据就会被覆盖导致答案错误*/
           dp[j] = max(dp[j], dp[j - i] + sum[i]);
       }
   }

   cout << dp[S] << endl;
   return 789113;
}