背包做法WA on #33 萌新悬赏关注求调
查看原帖
背包做法WA on #33 萌新悬赏关注求调
581928
jasonliujiahua楼主2023/8/5 13:27
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
int n,dp[maxn][4];
int gcd(int x,int y)
{
    if(y==0) return x;
    return gcd(y,x%y);
}
int lcm(int x,int y)
{
    return x*y/gcd(x,y);
}
signed main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    cin>>n;
    for(int i=0;i<=n;i++) dp[i][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=3;j++)
        {
            for(int k=1;k<=j;k++)
            {
                dp[i][j]=max(dp[i][j],max(dp[i-1][j],lcm(dp[i-1][j-k],i)));
            }
        }
    }
    cout<<max(max(dp[n][1],dp[n][2]),dp[n][3]);
    return 0;
}
2023/8/5 13:27
加载中...