最佳加法表达式

描述

给定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);
                }
            }
        }
    }
}