这道题题意不说，直接上思路：
根据n<=100可以看出答案可能为50位(111111......)所以对于longlong来说是存不下，所以我们设计状态要尽量避免数据过大，这对
空间或时间来说都是一种考验，我们用d(i,j)表示除以m余j的i位数所需要最少火柴数，所以状态转移方程为：
(此处采用刷表法) d[i+1][(j*10+k)%m] = min(d[i+1][(j*10+k)%m]，d[i][j]+c[k])
然后我们通过这样需要最大的数，首先最大的数一定满足位数最大，在位数最大的基础上满足从高位到低位数最大，
所以我们首先需要找到d[i][0]不是INF(在这里如果当前位凑不成我们设为INF)，在此基础上我们从9-0去试，然后求出900....%m的数n，
然后满足d[i-1][m-n]+c[9]<=n，如果满足要求9就可以，然后依次类推，注意细节以及dp初始化。
下面是实现：
// UVa 12105 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 50 + 5; // 100 / 2 const int maxm = 3000 + 5; const int INF = 10000000003; const int c[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; int n, m; int d[maxn][maxm], p[10][maxn]; void init() { for (int i = 0; i < 10; ++i) p[i][1] = i % m; for (int i = 2; i <= n / 2; ++i) for (int j = 0; j < 10; ++j) p[j][i] = p[j][i-1] * 10 % m; } void print_ans() { int Max_len, Vis = 1, M = 0; for (Max_len = n / 2; Max_len >= 0; --Max_len) if (d[Max_len][0] != INF) break; while (Max_len) { for (int i = 9; i >= 0; --i) { int mode = (p[i][Max_len]+M) % m; if (d[Max_len-1][(m-mode)%m]+c[i] <= n) { printf("%d", i); n -= c[i]; M = mode; Vis = 0; break; } } Max_len--; } if (Vis) printf("-1"); } int main() { int kase = 0; while (scanf("%d", &n) == 1 && n) { scanf("%d", &m); init(); for (int i = 0; i <= n / 2; ++i) for (int j = 0; j < m; ++j) d[i][j] = INF; d[0][0] = 0; for (int i = 0; i <= n / 2; ++i) for (int j = 0; j < m; ++j) if (d[i][j] != INF) for (int k = 0; k < 10; ++k) { int N = c[k] + d[i][j]; d[i+1][(j*10+k)%m] = min(N, d[i+1][(j*10+k)%m]); } printf("Case %d: ", ++kase); print_ans(); printf("\n"); } return 0; }
原文：https://www.cnblogs.com/yifeiWa/p/11298819.html