洛谷P1734 最大约数和 题解

题目链接：P1734 最大约数和

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

设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示只考虑前 i i i 个数总和不超过 j j j 的最大价值，则
d p [ i ] [ j ] = max ⁡ ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − i ] + v [ i ] ) dp[i][j]= max(dp[i-1][j],dp[i-1][j-i]+v[i]) dp[i][j]=max(dp[i−1][j],dp[i−1][j−i]+v[i])
v [ i ] v[i] v[i] 可以 O ( n log ⁡ n ) O(n log n) O(nlogn) 预处理

时间复杂度 O ( n 2 ) O(n^2) O(n2)

代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e3+15)

int n,v[N],dp[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    auto f = [=](int x)
    {
        for(int i=1; i*i<=x; i++)
            if(x%i==0)v[x]+=i+((x/i!=i)?(x/i):0);
        v[x]-=x;
    };
    for(int i=1; i<=n; i++) f(i);
    for(int i=1; i<=n; i++)
        for(int j=n; j>=i; j--)
            dp[j]=max(dp[j],dp[j-i]+v[i]);
    cout << dp[n];
    return 0;
}

转载请说明出处