题解 P1734 【最大约数和】

AFOier · 2016-08-22 13:31:15 · 题解

这题其实很简单，几乎裸的01背包

主要思路就是先把从1~s所有数的约数和算出来（如果数字比s大还有什么意义呢）

然后物品的重量（代码中用a数组存储）就是数字，物品价值就是约数和（代码中用b数组存储）

然后就是裸的01背包咯（而且只要一维）

#include <iostream>
using namespace std;
int s,a[1001],b[1001],f[1001]; //定义数组 
int ys(int p)
{
    int s1=0;
    for(int j=1;j<=p-1;j++)//注意它本身不算，所以要-1 
    if(p%j==0)s1+=j; //如果是这个数的约数，约数和就加上这个数 
    return s1;//返回约数和 
}
int main()
{
    cin>>s; //输入 
    for(int i=1;i<=s;i++)//计算1~s每个数的约数和 
    b[i]=ys(i),a[i]=i;//转化成01背包后，b数组储存的是价值（约数和），a数组储存的是重量（数字） 
    for(int i=1;i<=s;i++)
    {
        for(int j=a[i];j<=s;j++)
        {
            if(f[j]<=(f[j-a[i]]+b[i]))f[j]=f[j-a[i]]+b[i]; //一维01背包 
        }
    }
    cout<<f[s]; //输出 
}