题解 P1734 【最大约数和】

我不是小明 · 2018-03-22 20:14:13 · 题解

这道题很显然不用说是01背包

可以把数字约数的和看成是价值v[],而数字的值是重量w[],将这两个算出来后，就能直接套01背包模板了，是不是很简单？

#include<iostream>
using namespace std;
int f[10001],w[10001],v[10001],s;
int main()
{
    int i,j;
    cin>>s;
    for(i=1;i<=s;i++)
    {
        w[i]=i;
        for(j=1;j<=i/2;j++)
            if(i%j==0)//是约数 
                v[i]+=j;//累加 
    }
    for(i=1;i<=s;i++)//01背包模板。。 
        for(j=w[i];j<=s;j++)
            f[j]=max(f[j],f[j-w[i]]+v[i]);
    cout<<f[s]; 
    return 0;
}