uva12105 越大越好

给n根火柴棒，问能摆出的可以被m整除的最大数是多少。
n<=100 m<=3000
“摆出”的意思是以火柴棒作为电子显示屏上数字的一条边，比如1需要2根，2需要5根。

紫书上介绍了两种解法，代码仓库给出了最为简洁的第三种解法。本篇博客只分析快把我磨死了的第三种解法……

首先是dp的定义，简单来说，dp[i][j]表示“最长位数”，i表示“火柴数”，j表示“余数”。

具体来说，这个dp建立在这样一个过程上：从最高位到最低位逐位摆答案，那么在这个过程中的任意一个状态，它都有“已经摆好的部分”和“剩下还没摆的部分”这两个部分，比如说123____，其中123就是已经摆好的部分。一个dp[i][j]对应了一个这样的状态，其中i表示此时还剩下多少火柴，它是考虑剩下还没摆的部分的，j表示已摆数对m的余数，它是考虑已经摆了的部分的（在前例中j就是123对m的余数），而dp[i][j]表示此时没摆的数最多可能有多少位，需要保证摆完之后能被m整除，它是考虑剩下还没摆的部分。

在此定义下，本题的最终答案的位数就是d[n][0]，就是什么也没写的时候，相当于写下的部分是0，余数当然就是0，剩下的火柴数是n，d[n][0]就是剩下部分最大可能位数。

接下来看状态转移，对d[i][j]而言，已经写好的部分具体是多少是无所谓的，只需要知道它对m的余数是j，并且用掉了n-i根火柴。我们关心的是没有写的部分最长位数是多少，那么决策就来了，没有写的部分的首位只可能是0~9，容易理解，假如最优解里没有写的部分的首位是x，那么d[i][j]=d[i-k[x]][(10*j+x)%m]+1，其中k[x]是数字x的笔画数。枚举完x，即可递推出d[i][j]的值，与此同时，如果从大到小枚举x，还能得出在位数最大的前提下，下一位（也就是x）最大是多少，将这个最大的x记录在p[i][j]中，表示剩余i根火柴、已写数对m余j，并在确保未写数的位数最大的前提下，下一个数字最大写多少。

那么p[n][0]就表示什么都没写时，在确保未写数的位数最大的前提下，能写的第一个数最大是多少，然后转移到p[n-k[x]][(0*10+x)%m]，表示已写数满足限制，并确保未写数的数位最大，下一位最大写多少。以此类推，就能输出答案。

另外，再考虑初始条件，d[i][0]的状态表示还有i根火柴，前面的数已经能被m整除，那么至少有d[i][0]>=0，而d[0][j(>0)]则是无效状态，不应该参与后续的转移。对于不能由任何先前状态转移到的状态需要标记成无效，对于j==0的状态初始应标记为0。

源代码见代码仓库。