【Uva 12105】Bigger is Better

【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;
}