题目描述

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

输入输出格式

输入格式：

 

输入一个正整数S。

 

输出格式：

 

输出最大的约数之和。

 

输入输出样例

输入样例#1： 

11

输出样例#1： 

9

说明

样例说明

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

数据规模

S<=1000 把每个物品的约数看成权值，值看做重量，做01背包

1 #include
     
       2 #include
      
        3 using namespace std; 4 const int MAXN=1001; 5 inline char nc() 6 { 7     static char buf[MAXN],*p1=buf,*p2=buf; 8     return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++; 9 }10 inline int read()11 {12     char c=nc();int x=0,f=1;13     while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=nc();}14     while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}15     return x*f;16 }17 inline int work(int x)18 {19     int ans=0;20     for(int i=1;i
       
        =a[i].w;j--)39             dp[j]=max(dp[j],dp[j-a[i].w]+a[i].val);40     printf("%d",dp[n]);41 }