比赛场次 211
比赛名称 20130802初中
比赛状态 已结束比赛成绩
开始时间 2013-09-02 18:50:00
结束时间 2013-09-02 20:40:00
开放分组 全部用户
注释介绍
题目名称 添加号
输入输出 purasu.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 5 简单对比
用户 结果 时间 内存 得分

添加号

★☆   输入文件:purasu.in   输出文件:purasu.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

有一个由数字$1,2,…9$组成的数字串(长度不超过$8$),问如何将$M(M<=7)$个加号"$+$"插入到这个数字串中,使所形成的算术表达式的值最小。请编一个程序解决这个问题。

注意:加号不能加在数字串的最前面或最末尾,也不应有两个或两个以上的加号相邻。

$M$保证小于数字串的长度。

例如:数字串$79846$,若需要加入两个加号,则最佳方案为$79+8+46$,算术表达式的值$133$。

【输入格式】

第一行是一个数字串(数字串中间无空格),第二行是一个正整数$M$。

【输出格式】

所求得的最小和的精确值。

【样例输入】

79846
2

【样例输出】

133

【提示】

$30$%的数据,$M=1$。

$50$%的数据,$M<=2$。

$100$%的数据,数字串长度不超过$8$,$M<=7$。

【来源】

$2012$年河南省青少年信息学(计算机)奥林匹克赛竞赛(初中组)

$[NOI$ $1996]$添加号 简化版$(cogs$ $124)$