企业官网建设流程全解析

题目：P1734 最大约数和

题目描述

选取和不超过S SS的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。

输入格式

输入一个正整数S SS。

输出格式

输出最大的约数之和。

输入输出样例 #1

输入 #1

11

输出 #1

9

说明/提示

【样例说明】

取数字4 44和6 66，可以得到最大值( 1 + 2 ) + ( 1 + 2 + 3 ) = 9 (1+2)+(1+2+3)=9(1+2)+(1+2+3)=9。

【数据规模】

对于100 % 100 \%100%的数据，1 ≤ S ≤ 1000 1 \le S \le 10001≤S≤1000。

代码（一维数组）

#include<bits/stdc++.h>usingnamespacestd;constintM=1000+10;intV,n,cnt,w[M],v[M],f[M];intmain(){cin>>V;for(inti=1;i<=V;i++){cnt++;v[cnt]=i;for(intj=1;j<i;j++){if(i%j==0){w[cnt]+=j;}}}n=cnt;for(inti=1;i<=n;i++)for(intj=V;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]);cout<<f[V];return0;}

结果