题目描述
有 \(n\) 根火柴 \(m\) 种数字,数字 \(1,2,3,4,5,6,7,8,9\) 分别需要 \(2,5,5,4,5,6,3,7,6\) 根火柴,要求 \(n\) 根火柴全部都用完且拼成的数字最大,输出这个数字。
输入格式
第一行两个整数 \(n\),\(m\);
第二行 \(m\) 个整数,分别为 \(a_1,a_2,...,a_m\)(即 \(m\) 种数字是哪几个)。
输出格式
一行一个整数,表示能拼成的最大数字。
题解
做这个题的思路其他题解都讲得很完整了,从完全背包角度进行解决的解法(代码)也基本一样。但是在本人阅读题解时,遇到的问题就是不知道为什么有这样一句 f[0] = 1
,所以这里主要讲解一下代码中 f[0] = 1
的意义。
这里以样例一进行讲解:
样例一
20 4
3 7 8 4
f数组的更新状况如下:
||||||||||||||||||||||
||||||||||||||||||||||
||||||||||||||||||||||
||||||||||||||||||||||
||||||||||||||||||||||