Java实现蓝桥杯算法训练最大的算式

算法训练最大的算式

时间限制：1.0s 内存限制：256.0MB

问题描述

　　题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如：

　　N=5，K=2，5个数字分别为1、2、3、4、5，可以加成：

　　12(3+4+5)=24

　　1*(2+3)(4+5)=45

　　(12+3)*(4+5)=45

　　……

输入格式

　　输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中（2<=N<=15, 0<=K<=N-1）。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。

输出格式

　　输出文件仅一行包含一个整数，表示要求的最大的结果

样例输入

5 2

1 2 3 4 5

样例输出

120

样例说明

　　(1+2+3)45=120

package 第十九次模拟;

import java.util.Scanner;

public class 最大的算式 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		int k = sc.nextInt();

		int [] sum = new int [n+1];

		int [] num = new int [n+1];

		for (int i = 1; i <=n; i++) {

			num[i]=sc.nextInt();

			sum[i]=sum[i-1]+num[i];

//			System.out.print(sum[i]);

		}

		sc.close();

		long dp [] [] = new long [n+1][k+1];

		for (int i = 1; i <=n; i++) {

			dp[i][0]=sum[i];

		}

		//dp[i][j]是第i位数用了j个乘

		for (int i = 2; i <=n; i++) {

			for (int j = 1; j <=Math.min(i-1, k); j++) {

				for (int j2 = 2; j2 <=i; j2++) {

					dp[i][j]=Math.max(dp[i][j], dp[j2 - 1][j - 1] * (sum[i] - sum[j2 - 1]));

				}

			}

		}

		System.out.println(dp[n][k]);

	}

}

import java.util.Scanner;

public class 最大的算式 {

	  //求取数组A[start]到A[end]之间元素总和

    public static long getSum(int[] A, int start, int end) {

        long sum = 0;

        for(int i = start;i <= end;i++)

            sum += A[i];

        return sum;

    }

    /*

     * 参数start：数组A中开始划分元素的起始位置

     * 参数multi:进行乘法运算的个数

     */

    public static long getMax(int[] A, int start, int multi) {

        if(multi == 0)//当没有乘法的时候把后面的都加起来

            return getSum(A, start, A.length - 1);

        long max = 0;

        for(int i = start;i < A.length - 1;i++) {

            //此处i < A.length - 1原因是递归时start = i + 1，且start要小于等于A.length - 1

            long tempMax = getSum(A, start, i) * getMax(A, i + 1, multi - 1);

            max = (max < tempMax ? tempMax : max);

        }

        return max;

    }

    public static void main(String[] args){

        Scanner in = new Scanner(System.in);

    //    System.out.println("请分别输入一个整数n和一个整数k：");

        int n = in.nextInt();

        int k = in.nextInt();

        int[] A = new int[n];

        for(int i = 0;i < n;i++)

            A[i] = in.nextInt();

        System.out.println(getMax(A, 0, k));

    }

}

巴特西

Java实现蓝桥杯算法训练最大的算式

最新文章

热门文章

巴特西

Java实现 蓝桥杯 算法训练 最大的算式

最新文章

热门文章

Java实现蓝桥杯算法训练最大的算式