MENU

最佳加法表达式(二)

November 5, 2018 • Read: 252 • 算法

描述

给定n个1到9的数字,要求在数字之间最多添加m个加号(加号两边必须有数字),使得所得到的加法表达式的值最小,并输出该值。

输入

每组数据三行。第一行是整数n,表示有n个数(0<n≤10)
第二行是整数m,表示可以使用m个加号
第三行有n个数a~i~(1≤a~i~≤9)

样例输入

5
3
1 2 3 4 5

样例输出

24

样例解释

12+3+4+5

解题思路

动态规划常规题目,首先声明数组下标均从1开始。

因为可能会用到数字中某一段的数据,比方说234或者1234,所以用一个二维数组num[][]进行存储,表示从第i个数到第j个数的值为numi,例如对于样例来说,num3=345

既然是动态规划,就要将中间值保存起来,所以用一个二位数组res[][]进行存储,表示前i个数中放j个加号的最小值为resi,例如对于样例来说res3=15,最终答案就应该是resn

变量都定义完了,接下来就是算法思路。整个过程其实就是一个二重循环枚举加号的个数,那么就分三种情况:第一,加号个数等于0,没有加号,那resi=num1;第二,加号个数大于等于数的个数,假设当前枚举s个数,那么就一共有s-1个空隙可以插入加号,但是加号个数大于s-1,结果肯定就有问题,加号多,对于这种情况我们直接将res[i][j=INF;第三种情况,言外之意就是加号个数不等于0并且加号个数不大于数的空隙,对于这种情况我们就要再进行一重枚举,枚举放1个加号的时候,最小值是多少,枚举放2个加号的时候,最小值是多少,一直枚举到加号放万。

代码

import java.util.Scanner;

public class Main {
    static int n,m;//n个数字,m个加号
    static int arr[];
    static int num[][];//i到j的数字串
    static int min;//最小值
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        m = cin.nextInt();
        arr = new int[n + 1];
        num = new int[n + 1][n + 1];
        for(int i = 1;i <= n;i++) 
            arr[i] = cin.nextInt();
        //预处理数字串
        for(int i = 1;i <= n;i++) {
            num[i][i] = arr[i];
            for(int j = i + 1;j <= n;j++)
                num[i][j] = num[i][j - 1] * 10 + arr[j];
        }
        long[][] res = new long[n + 1][n + 1];//前i个数放j个加号的最小值
        for(int i = 1;i <= n;i++) {//枚举数
            for(int j = 0;j <= m;j++) {//枚举加号
                if(j >= i) //加号大于等于数的个数,∞
                    res[i][j] = Integer.MAX_VALUE;//非法状态
                else if(j == 0) //没有加号
                    res[i][j] = num[1][i];
                else {//能执行这里,表明j != 0 && i > j 意味着加号个数一定不比可放加号的位置多
                    long min = Integer.MAX_VALUE;
                    for(int k = 1;k <= j;k++)//枚举加号个数
                        min = Math.min(min,res[i - k][j - 1] + num[i - k + 1][i]);
                    res[i][j] = min;
                }
            }
        }
        System.out.println(res[n][m]);
    }
}

代码里面有一段是最重要的

min = Math.min(min,res[i - k][j - 1] + num[i - k + 1][i]);

这段代码表示的含义是:假设当前枚举到k个加号,那么此时最小值为i-k个数使用j-1个加号的加上剩下的后面一串数字串,也就是第i-k+1到i形成的数字串

举个例子,假设现在枚举到的i为5,也就是前5个数,j为3,也就是3个加号,那么第一次执行更新min值的含义为:前4个数放2个加号的最小值加上5到5位置之间形成的数字串

第二次更新min值的含义为:前3个数放2个加号的最小值加上4到5位置之间形成的数字串

后面的更新都没有意义了,因为前2个数2个加号,也就是res2的值是INF,一定不会更新min

Archives Tip
QR Code for this page
Tipping QR Code