最佳加法表达式

描述展开目录

给定 n 个 1 到 9 的数字，要求在数字之间最多添加 m 个加号 (加号两边必须有数字，并且不能有两个或两个以上加号相邻），使得所得到的加法表达式的值最小，并输出该值。

输入展开目录

每组数据三行。第一行是整数 n，表示有 n 个数 (0<n≤10)
第二行是整数 m，表示最多可以使用 m 个加号
第三行有 n 个数，每个数的范围都是 1 到 9

样例输入展开目录

5
3
1 2 3 4 5

样例输出展开目录

51

样例解释展开目录

12+34+5=51

解题思路展开目录

1. 剪枝展开目录

首先考虑可以考虑剪枝，总共只有 (n-1) 个位置可以放加号，并且不能有两个或以上的加号相邻，因此加号最多可以用 (n-1)/2 个，再引入贪心的策略，加号越多肯定值越小，所以，如果 m≤(n-1)/2，那就用 m 个，如果 m>(n-1)/2，那就只用 (n-1)/2 个

2.dfs展开目录

首先声明，所有的下标均从 0 开始。用 dfs (int idx) 来枚举所有加号摆放的位置，当 idx==m 时，就计算产生的值，然后更新最小值。dfs (idx) 表示的含义是当前用了 idx 个加号，所以 main 函数里调用 dfs (0)。然后是 dfs 函数体里如何枚举的问题，很简单用一层 for 循环，表示枚举到的位置 i，i<n-1

加号放的位置存在 mark [] 数组里，对于样例 12+34+5，对应的 mark [] 数组值为 mark [0]=1，mark [1]=3。num 数组的作用主要是存放数字列，例如 num0 = 12345，num2=34，方便后面直接用

dfs 函数里枚举完加号之后，如何计算也是一个问题，其实也比较简单，定义两个指针 i,j，j 一直往后遍历，当 j 遍历到 mark [index] 时，就将 numi 的值加在 sum 里，然后 i = j+1,index++，但是这样还有最后一个加号到最后一个数之前的值没加，所以最后还要加上 num [mark [index - 1] + 1][n - 1]

3. 分析时间复杂度展开目录

一个加号就要枚举一遍数字列，m 个加号要枚举 m 次数字列，数字列长度是 n，所以时间复杂度是 O (mn^2^)，暂时没想到什么地方如何用动态规划优化，重复计算的部分比较难想，可能我蒟蒻吧.....

代码展开目录

C展开目录

#include <stdio.h>
#include <algorithm>
using namespace std;

int n,m;//n和m如题所述
int ans = 0x7fffffff;//最终答案，要找最小值所以初始化为int最大值
int mark[10];//记录放加号的位置，第1个加号的位置在mark[0]
int arr[10];//n个数
int num[10][10];//num[i][j]表示i到j的数字串

void dfs(int idx)//当前用了idx个加号 
{
    if(idx == m)//加号用完了，计算产生式的值 
    {
        int sum = 0;
        int index = 0;
        int i = 0;
        for(int j = 0;j < n;j++)
        {
            if(j == mark[index])
            {
                sum += num[i][j];
                index++;
                i = j + 1;
            }
        }
        sum += num[mark[index - 1] + 1][n - 1];
        ans = min(ans,sum); 
        return;
    }
    for(int i = 0;i < n - 1;i++)
    {
        if(idx == 0)//第一个加号 
        {
            mark[idx] = i;
            dfs(idx + 1);
        }
        else
        {
            if(abs(mark[idx - 1] - i) > 1)//必须满足两个加号之间的距离大于1 
            {
                mark[idx] = i;
                dfs(idx + 1);
            }
        }
    }
} 
int main()
{
    scanf("%d",&n);
    scanf("%d",&m);
    for(int i = 0;i < n;i++) 
    {
        scanf("%d",&arr[i]);
        num[i][i] = arr[i];//i到i产生的数字串就是这个数字自己 
    }
    if(n == 1) //就一个数就直接输出结束 
    {
        printf("%d",arr[0]);
        return 0;
    }
    //预处理num数组 
    for(int i = 0;i < n;i++) 
        for(int j = i + 1;j < n;j++) 
            num[i][j] = num[i][j - 1] * 10 + arr[j];
            
    //剪枝m
    if(n > 2 && m > (n - 1) / 2)
        m = (n - 1) / 2;
        
    dfs(0);//开始搜索 
    printf("%d",ans);
    return 0;
}

Java展开目录

import java.util.Scanner;
public class Main {
    static int n, m, ans = 0x7fffffff;
    static int[] mark = new int[10];// 放加号的位置
    static int[] arr = new int[10];
    static int[][] num = new int[10][10];

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();// 数字个数
        m = cin.nextInt();// 加号个数
        for (int i = 0; i < n; i++) {
            arr[i] = cin.nextInt();
            num[i][i] = arr[i];
        }
        if (n == 1)//特殊情况，一个数就不用添加加号了，直接输出
            System.out.println(arr[0]);
        else {
            for (int i = 0; i < n; i++)
                for (int j = i + 1; j < n; j++)
                    num[i][j] = num[i][j - 1] * 10 + arr[j];
            for (int i = 0; i < mark.length; i++)
                mark[i] = -1;
            if(n > 2 && m > (n - 1) / 2)//剪枝，有可能根本放不了那么多加号
                m = (n - 1) / 2;
            dfs(0);
            System.out.println(ans);
        }
    }

    static void dfs(int idx) {// 已经用了idx个加号
        if (idx == m) {//加号用完则开始计算产生的值
            int sum = 0;
            int index = 0;
            int i = 0;
            for (int j = 0; j < n; j++) {
                if (j == mark[index]) {
                    sum += num[i][j];
                    index++;
                    i = j + 1;
                }
            }
            sum += num[mark[index - 1] + 1][n - 1];
            ans = Math.min(ans, sum);
            return;
        }
        for (int i = 0; i < n - 1; i++) {// 枚举放加号的位置
            if (idx == 0) {
                mark[idx] = i;
                dfs(idx + 1);
            } else {
                if (Math.abs(mark[idx - 1] - i) > 1) {
                    mark[idx] = i;
                    dfs(idx + 1);
                }
            }
        }
    }
}