题解 P1734 【最大约数和】
HoshiuZ
·
·
题解
思路
本题实质就是一个背包问题。s为背包的容量，物品则为1到s间的所有数，物品的体积就是数的值，而价值则为数的除了本身的因子和。定义fsum(x)为x的非本身因子和，那么本题的状态转移方程便很容易得到了。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int s,dp[1010];
int fsum(int x) {
int sum=0;
for(int i=1;i<x;i++) {
if(!(x%i)) sum+=i;
}
return sum;
}
int main() {
cin>>s;
for(int i=1;i<=s;i++) {
for(int j=s;j>=i;j--) {
dp[j]=max(dp[j],dp[j-i]+fsum(i));
}
}
cout<<dp[s]<<endl;
return 0;
}
```