题解

1 条题解

  • 1
    @ 2022-06-05 22:05:17
    #include<bits/stdc++.h>
    #define N 1005
    using namespace std;
    int s,c[N],f[N];
    int work(int n)//求n的约数和
    {
        int t=1,i;
        for(i=2; i*i<n; i++)
            if(n%i==0)
                t+=i+n/i;
        if(i*i==n)
            t+=i;
        return t;
    }
    int main()
    {
        cin>>s;//将s看做背包的最大承重
        for(int i=1; i<=s; i++)
            c[i]=work(i);//将数i的约数和看做是第i件物品的价值(转化为背包问题)
        for(int i=1; i<=s; i++)
            for(int j=s; j>=i; j--)//将数i的大小看做是第i件物品的重量(转化为背包问题)
                f[j]=max(f[j-i]+c[i],f[j]);
        cout<<f[s]<<endl;
        return 0;
    }
    
    
  • 1

信息

ID
1188
难度
4
分类
动态规划 | 背包 点击显示
标签
递交数
4
已通过
1
通过率
25%
上传者