#P3324. [Scoi2013]火柴棍数字

    ID: 2512 传统题 1000ms 512MiB 尝试: 66 已通过: 22 难度: 7 上传者: 标签>难度分类提高+/省选-动态规划线性 DP状态维度消除贪心支配关系构造与建模序列构造位运算位计数CF2300

[Scoi2013]火柴棍数字

题目描述

Fish 在人类丢弃的物品里找到了许多火柴棍,用它们拼成一个有 nn 位的十进制数。数字 00 至 99 的拼法如下图。

数字 0 至 9 的火柴拼法

每个数位占据的宽度和各根火柴棍的位置都是固定的,因此下列两种拼法都不合法:直接从 66 移走四根留下的两根不在数字 11 的规定位置;直接从一个 88 移走三根留下的四根不占两个数位,不能当作 1111。

数字固定占位的两种不合法变换

Fish 想移动至多 kk 根火柴棍,把数变得尽量大。最低位紧挨着墙,不能在最低位后面添加数位,可以在最高位前面添加数位。火柴棍不能折断或丢弃。火柴头的朝向不影响数字识别,例如下列拼法都是数字 11。

同一位置的火柴头可朝任一方向

输入格式

从标准输入读取。一行,包含一个没有前导零的 nn 位十进制数 xx,以及整数 kk。

输出格式

向标准输出写入。输出一行,表示移动至多 kk 根火柴棍后能得到的最大数。

样例 1

3 2
17

样例 2

3 3
71

样例说明

第一组把 33 中间和底部的两根火柴移到左边,拼出新的十位 11,原数位成为 77。第二组移动 33 上、中、下方的三根火柴,在左边拼成 77,原数位成为 11。

两个样例中的火柴移动方式

数据范围

对于 30%30\% 的数据,1≤n≤101\le n\le10,0≤k≤100\le k\le10。

对于所有数据,1≤n≤5001\le n\le500,0≤k≤35000\le k\le3500。