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