首页 > 试题广场 >

整数成绩最大化

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

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

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

例如：

2=1+1，输出1；

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

输入描述:

输入为1个整数

输出描述:

输出为1个整数

示例1

输入

输出

算法知识视频讲解

马什么梅呀

很简单：动态规划

用数组res保存结果，对于一个数n，其最大化结果为res[n]

n=a+b，res[n] = max(res[a],a)*max(res[b],b)

举例说明：我这里计算到6

res[1]=1
res[2]=1*1
res[3] = max(2,res[2])*max(res[1],1)
res[4] = max{ max(1,res[1])*max(res[3],3)，max(2,res[2])*max(res[2],2) }
res[5] = max{ max(1,res[1])*max(res[4],4)，max(2,res[2])*max(res[3],3) }
res[6] = max{ max(1,res[1])*max(res[5],5)，max(2,res[2])*max(res[4],4) ，max(3,res[3])*max(res[3],3)}

//整数成绩最大化
#include<bits/stdc++.h>
using namespace std;

int main(){     int n,aim,j,i;     int tem,a,b;     int res[10000]={0};//用来存到该位置的最大值      while(scanf("%d",&n)!=EOF){         res[1]=1;         if(n==1){             ;         }else{             for(aim=2;aim<=n;aim++){//计算到i                  tem = 1;                 for(i=1;i<=aim/2;i++){                     j = aim-i;                     a = i;                     b=j;                     if(a<res[i]){                         a = res[i];                     }                     if(b<res[j]){                         b = res[j];                     }                         if(a*b>tem){                         tem = a*b;                     }                 }                 res[aim]=tem;             }         }         printf("%d\n",res[n]);     }     return 0;
}

发表于 2018-10-19 17:24:55 回复(2)

向宇回桌

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int three = n / 3;
        if (((n - three * 3) & 1) == 1) { three--; }
        int two = (n - three * 3) / 2;
        int result = (int)(Math.pow(3, three) * Math.pow(2, two));
        System.out.println(result);
    }
}

发表于 2019-02-28 18:39:26 回复(2)

Python

TimeMac

解释：最大收益是3，余数为1则分给其中一个3,得到4，余数为2则乘上去
所以只需要列举出递推的前三项，第4、5、6项，然后递推a[i]=a[i-3]*3
为什么不是最大收益不是4以上呢？例如5，5可分解为2*3收益能通过继续分解得到增加。
前几个并不能通过递推公式得到，所以列举出来。

1. num = int(input())
2. resultList = [0,0,1,2,4,6,9]
3. if num<7:
4.     print(resultList[num]) 
5. else:
6.     for i in range(7,num+1):
7.         resultList.append(resultList[i-3]*3) 
8. print(resultList[num])

编辑于 2018-09-15 23:45:24 回复(3)

qyq明天会更好


import java.util.Scanner;
public class Main {
    /*
     * 举例计算11,11=5+6,5*6=30,11=3+4+5,3*4*4=48,11=2+3+3+3,2*3*3*3=54,11=1
     */
    static int p(int num) {
        int maxMul = 1;
        //i表示分解为i个数的加法，这些数相差不超过1.在所有的分解法中选择乘积最大的。
        for (int i = 2; i < num; i++) {
            int rem = num % i;
            int quo = num / i;
            int mul = 1;
            // int j=1;
            for (int j = 1; j <= i - rem; j++)
                mul *= quo;
            for (int j = 1; j <= rem; j++)
                mul *= (quo + 1);
            if (mul > maxMul)
                maxMul = mul;
            else
                return maxMul;
        }
        return maxMul;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
//        int num=2;
//        num=10;
        Scanner scanner=new Scanner(System.in);
//        返回：从输入信息扫描的 int
        int num=scanner.nextInt();
        System.out.println(p( num));
        
    }
}

发表于 2018-08-19 08:37:10 回复(0)

乔碧萝殿下

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sum = (int)Math.pow(3, (n / 3 - 1));
        if(n % 3 == 1)
            sum *= 4;
        if(n % 3 == 2)
            sum *= 3 * 2;
        if(n % 3 == 0)
            sum *= 3;
        System.out.println(sum);              
    }
}

发表于 2019-03-17 15:43:52 回复(0)

hujianbest

简单的java解法，有不正确的地方还请指正

import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        System.out.println(Doit(num));
    }
    //最优化问题，尽量都分成3，不足部分就分成2
    public static long Doit(int num) {
        long result = 1;
        while(num>4){
            result = result*3;
            num=num-3;
        }
        result = result * num;
        return result;
    }
}

发表于 2018-08-30 15:12:34 回复(2)

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)

Python

Jancydc

def solution(n):
    if n<=3:return n-1
    if n==4:return n
    if n>4:
        if n % 3 ==2:
            return 2 * 3**(n//3)
        elif n %3 ==1:
            return 4*3**(n//3-1)
        else:
            return 3**(n//3)
if __name__ =='__main__':
    n = int(input().strip())
    print(solution(n))

这是一道找规律的题

n 1 2 3 4 5 6 7 8 9 10 ...

max 0 1*1 1*2 2*2 2*3 3*3 2*2*3 2*3*3 3*3*3 2*2*3*3 ...

编辑于 2020-06-23 11:12:40 回复(0)

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long num,m;
    cin>>num;
    if(num<4)
        cout<<num-1<<endl;
    if(num%3==1)
        m=pow(3,num/3-1)*4;
    else if(num%3==0)
        m=pow(3,num/3);
    else 
        m=pow(3,num/3)*(num%3);
    cout<<m<<endl;
    return 0;
}

发表于 2019-06-21 19:35:23 回复(0)

改个名求offer

好像大家都没有考虑负数？

#include<bits/stdc++.h>
using namespace std;
int a[6]={0,0,1,2,4,6};
int cal(int x,int y)
{
    if(x<6&&y==0)
    {
        return a[x];
    }
    else
    {
        if(x-3==0)
            return 3;
        if(x-3==1)
            return 4;
        if(x==5)
            return 6;
        if(x>5)
            return 3*cal(x-3,1);
    }
    return 0;
}
int main()
{
    int n,i;
    long long ans;
    scanf("%d",&n);
    n=abs(n);
    ans=cal(n,0);
    printf("%lld\n",ans);
}

发表于 2019-02-14 09:45:08 回复(0)

Python 3

TS9527

有两种方法解决该题：

解法一：动态规划

记数j的最大分解乘积为prod[j]。对于数k，我们可以依次遍历i = 1, ..., k - 1，计算i * prod[k - i]的最大值然后取max。当然了，这个过程当中可能存在k - i > prod[k - i]的情况（因为在统计prod[k - i]时，我们没有考虑k - i = 0 + (k - i)这种情况，不符合题目要求分解为两个正整数），这个时候我们要取的乘积就变成了i * (k - i)。也就是说，从数学上来说，有状态转移方程 $prod[k] = \max{}_{i = 1, .., k - 1} \max(i \times prod[k - i], i \times (k - i))$

根据这个方程遍历到n即可。

AC代码：

class MainActivity:

    def main(self):
        # Read the data
        n = int(input())
        # Initialization
        maxProd = [1]
        # Traverse
        for num in range(1, n):
            realNum = num + 1
            tmpResult = float('-inf')
            for subtractNum in range(1, realNum):
                subtractResult = realNum - subtractNum
                subtractResultIdx = subtractResult - 1
                tmpResult = max(tmpResult, subtractNum * maxProd[subtractResultIdx], subtractNum * subtractResult)
            maxProd.append(tmpResult)
        print(maxProd[-1])


if __name__ == '__main__':
    M = MainActivity()
    M.main()

这个时间复杂度应该在O(n²)的样子，AC运行时间是45ms。

解法二：数学（均值不等式）

我们假设可以把n分解为k个正整数 $a_1, a_2, ..., a_k$ ，那么该问题就变成了已知 $\Sigma_{i = 1}^{k}a_{i} = n$ 的前提下求 $\prod_{i = 1}^{k}a_i$ 的最大值。根据均值不等式 $(\prod_{i = 1} ^ {k}a_{i})^\frac{1}{k} \leq \frac{\Sigma_{i = 1}^{k}a_i}{k} = \frac{n}{k}$ ，我们很容易确定在 $a_i > 0$ 且为实数的情况下有 $\prod_{i = 1}^{k}a_i$ 的最大值为 $(\frac{n}{k})^k$ ，取得该最大值的条件是 $a_1 = a_2 = ... = a_k = \frac{n}{k}$ 。

然而，由于题目正整数的限制，我们只能让 $a_i$ 在 $\frac{n}{k}$ 周围取整（除非这个结果就是个整数，那直接取它就行）。我们记 $\lfloor\frac{n}{k}\rfloor = t$ ，则对于任意 $a_i$ 均应为 $t$ 或 $t + 1$ 。假设有 $p$ 个元素取 $t$ ，则会有 $k - p$ 个元素取 $t + 1$ 。根据题目限制，应有 $tp + (t + 1)(k - p) = n$ ，很容易解得 $p = kt + k - n$ 。因此，分解成 $k$ 个数的最大乘积应为 $t^{kt + k - n}\times(t + 1)^{n - kt}$ 。

我们遍历k = 1, ..., n，并每次取max，就可以得到最终结果，即最终结果为 $\max{}_{k = 1}^{n} \lfloor\frac{n}{k}\rfloor^{k\lfloor\frac{n}{k}\rfloor + k - n}\cdot(\lfloor\frac{n}{k} \rfloor+ 1)^{n - k\lfloor\frac{n}{k}\rfloor}$

AC代码：

class MainActivity:

    def main(self):
        # Read the data
        n = int(input())
        # Initialization
        result = float('-inf')
        # Traverse
        for k in range(1, n + 1):
            if n % k:
                lowNum = n // k
                highNum = lowNum + 1
                result = max(result, lowNum ** (k * lowNum + k - n) * highNum ** (n - k * lowNum))
            else:
                result = max(result, (n // k) ** k)
        print(result)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

遍历的时间复杂度是O(n)，但我感觉乘方也挺耗时间的，看乘方做快速幂优化才行吧。

发表于 2024-08-26 15:09:36 回复(0)

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)

冒险的梦

// 动态规划
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i/2; j++){
                dp[i] = Math.max(dp[i], Math.max(j,dp[j])*Math.max((i-j),dp[i-j]));
            }
        }
        System.out.println(dp[n]);
    }
}

发表于 2021-08-05 10:43:35 回复(0)

C/C++

codewind

#include<bits/stdc++.h>
using namespace std;
inline int getRes(int x) {
    if(x==2) return 1;
    if(x==1) return 1;
    if(x<0) return 1;
    if(x==3) return 3;
    int sum = 1;
    while(x>4) {
        sum = sum*3;
        x-=3;
    }
    return sum *x;
}
int main(void) {
    
    int f;cin>>f;
    cout << getRes(f) <<endl;
}

发表于 2021-04-10 13:02:21 回复(0)

Shelven丶

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int z, x, c = 1;
	cin >> z;
	if (z <= 4)cout << z;
	else
	{
		while (1)
		{
			z = z - 3;
			c *= 3;
			if (z == 4)
			{
				c *= 4;
				break;
			}
			else if (z < 3)
			{
				if (z == 0)break;
				else
				{
					c *= z;
					break;
				}
			}
		}
		cout << c;
	}
}

发表于 2020-04-11 16:35:49 回复(0)

Python

冉龙宇

动态规划问题

n = int(input().strip())
# 动态规划算法
maxli = [0, 1, 1]  # 存储每个数最大的乘积

for num in range(3, n+1, 1):
    maxnum = 0
    l = 1
    r = num-1
    while l<=r:
        maxnum = max(max(l, maxli[l])*max(r, maxli[r]), maxnum)
        l += 1
        r -= 1
    maxli.append(maxnum)

print(maxli[n])

编辑于 2019-08-30 14:23:05 回复(0)

C/C++

海问香12138

其他语言永远也体会不到C语言的快乐（尤其是C++）

#include <stdio.h>

#define MAXN 1010

long long n;
long long ans[MAXN];

long long max(long long a,long long b);

int main()
{
	long long i,j;
	ans[1] = 1;
	ans[2] = 2;
	for(i=3;i<MAXN;i++)
		for(j=1;j<=(i>>1);j++)
			if(max(j,ans[j])*max(i-j,ans[i-j])>ans[i])
				ans[i] = max(j,ans[j]) * max(i-j,ans[i-j]);
	scanf("%lld",&n);
		printf("%lld\n",ans[n]);
	return 0;
}

long long max(long long a,long long b)
{
	return a>b?a:b;
}

发表于 2019-08-19 11:12:48 回复(0)

,chaser

import java.util.Scanner;

public clas***ain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        if (n == 1 || n == 2) {
            System.out.println(1);
            return;
        }

        int res = 0;

        for (int i = 2; i <= n / 2; i++) {
            int a = n / i;
            int b = n - a * i;
            if (b != 0){
                re***ath.max(res, (int)Math.pow(a,i)*b);
            } else {
                re***ath.max(res, (int)Math.pow(a,i));
            }

        }
        System.out.println(res);

    }
}

编辑于 2019-05-21 10:37:15 回复(0)

C/C++

咸鱼儿

#include<stdio.h>
int fun(int n)
{
    if(n>4)
    {
        return 3*fun(n-3);
    }
    else
    {
        return n;
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    printf("%d\n",fun(n));
}

发表于 2019-05-07 21:51:47 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师 PHP工程师贪心动态规划 2018 数学 Java工程师招商银行信用卡中心

上传者：小小

难度：

32条回答 76收藏 5946浏览

通过挑战的用户

查看代码

牛客68457...

2023-03-04 19:55:50
优秀的大魔王不愿吃饼

2023-01-11 16:44:39
liu12345

2022-10-01 17:39:15
getmsi

2022-09-25 19:35:25
牛客11351...

2022-09-19 10:46:48

整数成绩最大化

输入描述:

输出描述:

输入

输出

解法一：动态规划

解法二：数学（均值不等式）

问题信息

热门推荐

通过挑战的用户

相关试题