P3283 [SCOI2013]火柴棍数字

    • 19通过
    • 77提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 容斥 深度优先搜索,DFS 线性基 2013 四川 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Fish是一条生活在海里的鱼,有一天他很无聊,于是他去捡了人类扔进海里的垃圾,打算用这些来玩些什么。

    他从捡回来的垃圾堆里找到了不少火柴棍,便把这些火柴棍拼成了一个长度为n 的十进制数,每个数字的拼法如下图所示

    注意:每个数字占据的宽度和摆放方式是固定的,故以下情况均不合法。

    拼完之后他好累,感觉再也不会拼了。他对拼出来的数大小不满意,希望通过移动一些火柴棍的位置来把这个数变得尽量大。

    由于太累,他只能最多移动k 根火柴棍。而且由于数字的最低位放在墙边,他不能在该数的低位后面添加数字,但他可以在该数的前面添加数字。

    你能帮他算出他移动火柴棍之后的数最大能是多大吗?

    注意:火柴棍对于Fish 来说是很贵重的物品,所以不允许折断或丢弃火柴棍。

    注意:火柴头的方向不影响数字的辨识,例如下面几种情况都是数字1

    输入输出格式

    输入格式:

    输入仅含一行,分别是长度为n 的十进制数x 和最多移动火柴棍的数量k。x 没有前导零。

    输出格式:

    输出仅一行,表示移动火柴棍之后的最大数。

    输入输出样例

    输入样例#1: 复制
    3 2
    
    输出样例#1: 复制
    71
    输入样例#2: 复制
    3 3
    输出样例#2: 复制
    71

    说明

    对于30% 的数据,1 <= n <= 10,0 <= k <= 10。

    对于100% 的数据,1 <= n <= 500,0 <=k <=3500。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。