　　题目大意

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

　　分析

　　　　　　把我们分解出来的因数进行合并，存在一个不知名的数组里，然后我们大可开始我们的迪屁！！（bag），我们可以

　　　　　　把它转化成0 1背包：

　　　　　　f[j]=max(f[j],f[j-1]+sum[i]);

　　　　于是：

　　code

 #include<cstdio>

 #include<iostream>

 using namespace std;

 int f[];

 int ans;

 int n;

 int sum[];

 int main(){

     freopen("maxsum.in","r",stdin);

     freopen("maxsum.out","w",stdout);

     cin>>n;

     for(int i=;i<=n/;i++){

         for(int j=i*;j<=n;j+=i){

             sum[j]+=i;

         }

     }

     for(int i=;i<=n;i++){

         for(int j=n;j>=;j--){

             if(j>=i)

                 f[j]=max(f[j],f[j-i]+sum[i]);

             ans=max(ans,f[j]);

         }

     }

     cout<<ans;

 }

大水

巴特西

【JZOJ】2126. 最大约数和

题目大意

分析

code

最新文章

热门文章