算法笔记_02:蓝桥杯练习 最大的算式

引用

1. 动态规划：最大算式

---

1 问题描述

<blockquote>
问题描述
　　题目很简单，给出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
</blockquote>
<p>

---

2 解决方案</h2>

<pre><big>题目分析：
Step 1:我们先考虑简单的情况，假设题目的输入是只有1个乘号。
对于1,2,3,4,5这个序列Q，在插入1个乘号的情况下，乘号的位置依次有4个。且乘号将这个序列分成了两部分，我们记为left,right。
显然，序列的计算值为leftright。
情况如下
left:1 right: 2+3+4+5
left:1+2 right: 3+4+5
left:1+2+3 right: 4+5
left:1+2+3+4 right: 5
我们只需枚举出所有情况，记录最大值即可
记录这个过程为f(Q)
Step 2:我们再考虑增加一个乘号的情况。
增加一个乘号的时候，我们假设第一个乘号位置固定在数字1后面，与上面一种情况相比，不考虑乘号的时候
left:1 right: 2+3+4+5
right是简单求和即可。
因为第一个乘号位置固定，我们只能在right序列中插入第二个乘号。我们对right序列再执行一遍上一步操作，就得到了序列(2,3,4,5)中插入1个乘号的最大值。记录右边序列为Qr,此时
left:1 right: f(Qr) (Qr = (2,3,4,5))
那么，如果有一个乘号在数字1后面， 算式的最大值就是 1f(Qr)
Step 3:同样的方法，我们可以计算固定第一个乘号的位置其他3种情况
left:1+2 right: f(Qr) (Qr = (3,4,5))
left:1+2+3 right: f(Qr) (Qr = (4,5))
left:1+2+3+4 right: f(Qr) (Qr = (5))
Step 4: 记录下这4种情况的算式最大值，就可以得到一个最终答案

结论：
根据以上分析，我们可以得出一个状态转移方程
记输入序列为Q,
S(Q,start,len)表示在序列Q中，从start位置开始长度为len的序列的和(即上面分析中的left)。
f(Q,start,len,mulcount)表示在序列Q中，从start位置开始长度为len的序列，向其中插入mulcount个乘号的最大算式值(即上面分析中的right)。

f(Q,start,len,mulcount) = max{ S(Q,start,leftlen) * f(Q, leftlen,len-leftlen, mulcount-1) | 0
</big></pre>
<u>具体java代码如下</u>

import java.util.Scanner;

//深度优先搜索递归法思想

public class 最大算式 {

    public long getSum(int[] A, int start, int end) {
        long sum = 0;
        for (int i = start; i <= end; i++) { // eg:start=0;end=1。理解i<=end.
            sum += A[i];
        }
        return sum;
    }

    public 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++) { // "start"—sum运算时起始位置;"i"—sum运算时截止位置
            long tempMax = getSum(A, start, i) * getMax(A, i + 1, multi - 1); // 深度搜索，递归
            max = (max > tempMax) ? max : tempMax;
        }
        return max;
    }

    public static void main(String[] args) {
        最大算式 test = new 最大算式();
        Scanner in = new Scanner(System.in);
        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(test.getMax(A, 0, k));
    }

}