最佳加法表达式

描述

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java爬坑系列

【JAVA零基础入门系列】Day10 Java中的数组

  什么是数组?顾名思义,就是数据的组合,把一些相同类型的数放到一组里去。   那为什么要用数组呢?比如需要统计全班同学的成绩的时候,如果给班上50个同学的成绩...

2006
来自专栏ACM算法日常

分割排序(排序)- HDU 1106

输入一行数字,如果我们把这行数字中的‘5’都看成空格,那么就得到一行用空格分割的若干非负整数(可能有些整数以‘0’开头,这些头部的‘0’应该被忽略掉,除非这个整...

731
来自专栏老九学堂

【必读】超全的C语言基础知识大全

我们用一个简单的c程序例子,介绍c语言的基本构成、格式、以及良好的书写风格,加深小伙伴们对C语言的认识。

2062
来自专栏专注研发

希尔排序(shell‘ sort)

希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序

953
来自专栏老九学堂

【必读】C语言基础知识大全

C语言程序的结构认识 用一个简单的c程序例子,介绍c语言的基本构成、格式、以及良好的书写风格,使小伙伴对c语言有个初步认识。 例1:计算两个整数之和的c程...

5138
来自专栏大闲人柴毛毛

剑指offer——面试题10输入一个十进制整数,统计其中二进制1的个数

/** * 题目:输入一个十进制整数,统计其中二进制1的个数 * @author 大闲人柴毛毛 */ public class CountBitOne {...

3514
来自专栏尾尾部落

[剑指offer] 链表中倒数第k个结点 [剑指offer] 链表中倒数第k个结点

经典的双指针法。定义两个指针,第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针保持不动,从第k步开始,第二个指针也开始从链表的头指针开始遍历,由于两个...

952
来自专栏我是攻城师

理解插入排序,希尔排序,选择排序的算法原理

在前面的文章中,其实已经把效率比较高的排序算法给分析过了,比如比较通用的快排,归并排序和堆排,还有用于特定场景的计数排序等。本篇我们把剩下的几种效率一般的排序算...

821
来自专栏从流域到海域

《笨办法学Python》 第19课手记

《笨办法学Python》 第19课手记 本节课讲函数和变量(变量和函数的关系是变量作为做函数的参数,定义时是形参,使用时是实参),内容比较简单。 源代码如下: ...

23110
来自专栏noteless

[二]基础数据类型之Long详解

toUnsignedString 系列   toString  toXXXString  系列

2183

扫码关注云+社区