【Link】:

【Description】



让你用最多n根棍子,组成一个数字,使得它能够被m整除;

数字1..9分别需要用…根棍子.

要求这个数字尽可能地大;

然后输出这个数字.

【Solution】



设f[i][j]表示i位数字,对m的取余结果为j,最少需要多少根棍子;

这个做一下简单的DP就能弄出来;

这里的f数组允许出现前导的0;

f数组弄出来以后;

枚举最后的答案有多少位i;

然后如果f[i][0]<=n;

则对第i位的x 从大到小枚举;

第i为是x的话;

能够推出来前i-1位组成的数字对m的取余结果应该是多少;

即(0−x∗10(i−1)+m) mod m

这里x要求大于0;

否则,如果有前导0的话,可能会漏解;

因为前导0的存在,它可能不是最大的整数;

但是从第i-1位到个位这一段的数字是可以有前导0的

所以f数组要考虑有前导0的情况



【NumberOf WA】



2



【Reviw】



这种求最大\最小的满足一定条件的题;

一般都是枚举;

然后用个工具函数判断..



【Code】

#include <bits/stdc++.h>

using namespace std;

const int N = 50;

const int M = 3000;

const int INF = 0x3f3f3f3f;

const int c[10] = {6,2,5,5,4,5,6,3,7,6};

int n,m;

int f[N+10][M+10];//f[i][j],i位数,取余结果为j最少需要多少根火柴

int pre[N+10];

vector <int> v;

bool fix(int x,int mod,int rest){

    if (x==0 && mod == 0) return true;

    if (x==0) return false;

    for (int i = 9;i >= 0;i--){

        if (i==0 && v.empty() && x!=1) return false;

        int now = (i*pre[x-1])%m;

        int need = (mod-now+m)%m;

        if (f[x-1][need]+c[i]<=rest){

            v.push_back(i);

            if (fix(x-1,need,rest-c[i])) {

                    return true;

            }

            v.pop_back();

        }

    }

    return false;

}

int main(){

    //freopen("F:\\rush.txt","r",stdin);

    int T = 0;

    while (~scanf("%d%d",&n,&m) && n){

        T++;

        for (int i = 0;i <= N;i++)

            for (int j = 0;j <= M;j++)

                f[i][j] = INF;

        f[0][0] = 0;

        for (int i = 0;i <= N-1;i++)

            for (int j = 0;j <= M;j++){

                if (f[i][j]<INF){

                    for (int k = 0;k <= 9;k++){

                        int tj = (j*10+k)%m;

                        if (f[i+1][tj]>f[i][j]+c[k])

                            f[i+1][tj] = f[i][j] + c[k];

                    }

                }

                if (i==1 && j==0 && f[i][j] >=INF) f[i][j] = c[0];

            }

        pre[0] = 1%m;

        for (int i = 1;i <= N;i++)

            pre[i] = (pre[i-1]*10)%m;

        bool solved = false;

        for (int i = N;i >= 1;i--)

            if (f[i][0]<=n){

                v.clear();

                solved |= fix(i,0,n);

                if (solved) break;

            }

        printf("Case %d: ",T);

        if (!solved)

            puts("-1");

        else {

            for (int x:v)

                printf("%d",x);

            puts("");

        }

    }

    return 0;

}