整数成绩最大化

[编程题]整数成绩最大化

热度指数：2646 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个整数n，将n分解为至少两个整数之和，使得这些整数的乘积最大化，输出能够获得的最大的乘积。

例如：

2=1+1，输出1；

10=3+3+4，输出36。

输入描述:

输入为1个整数

输出描述:

输出为1个整数

示例1

输入

输出

算法知识视频讲解

Java

牛客138387224号

// 动态规划

// M[i]表示数字i所能有的最大乘积。数字 i 可以分为（i-j）和 j 两部分（j<i），而 M[j] 已经代表了 j 拥有最大乘积的情况（不论j被分为几个）

// 主要问题是在 i > 2时，j可以选择被拆分然后看乘积（M[j])，也可能直接使用自身（因子数已经为2了)

import java.util.*;

public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int input=sc.nextInt();

// DP:
int[] M=new int[input+1];
M[0]=0;
M[1]=1;
M[2]=1;

if(input<=2){
System.out.println(1);
}
for(int i=3;i<=input;i++){
for(int j=1;j<i;j++){
M[i]=Math.max(M[i],(i-j)*(Math.max(M[j],j)));
}
}

System.out.println(M[input]);
}
}

发表于 2022-08-09 13:27:17 回复(0)

Java

cc114

import java.util.*;

public class Main{
    public static int[] res;
    public static int solu(int n){
        if (n <= 1) return 1;
        if (res[n] != 0) return res[n];
        int maxValue = 0;
        for (int i = 1;i<=n;i++){
            maxValue = Math.max(maxValue, i * Main.solu(n-i));
        }
        res[n] = maxValue;
        return maxValue;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        Main.res = new int[n+1];
        if (n == 2){System.out.println(1);}
        if (n == 3){System.out.println(2);}
        else{
            System.out.println(Main.solu(n));
        }
    }
}

发表于 2022-05-09 18:07:35 回复(0)

Java

pein531

首先要知道，任何大于3的数都可以拆成若干2和3之和。而只要大于4的数，为了乘积尽可能大，尽量拆3出来乘，最后剩下的数小于等于4的话就不拆了。小于4只可能是3和2，直接累乘到结果上，等于4同样累乘到结果上，相当于拆出了两个2相乘。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if(n <= 3){
            System.out.println(n - 1);
        }else{
            int res = 1;
            while(n > 4){
                res *= 3;
                n -= 3;
            }
            System.out.println(res * n);
        }
    }
}

发表于 2022-01-14 23:34:16 回复(0)