【Link】:https://csacademy.com/contest/round-39/task/seven-segment-display/

【Description】



0..9各自有一个数字,代表组成它需要几根棍子;

给你k根棍子,然后问你这k根棍子能够组成的最小数字是多少;

【Solution】



数位DP;

设b[0..9]表示对应下标的数码要多少根棍子组成;

设f[i]表示i根棍子能否组成一个数字,如果能的话,组成的数字最小是由几个数码组成的;

(为INF表示不能组成);

f[0] = 0;

然后对于f[i];

f[i+b[0..9]] = min(f[i+b[0..9]],f[i]+1);

表示把0或1或..9放在原先组成的数后面;

O(N∗10)的递推就能弄出f数组;

然后对于f[k];

先判断f[k]是否为INF;

不是INF;

则能够确定最后答案的位数了;

如果f[k]==1;

则第一位可以为0;

否则,第一位不能为0;

因为0和6的棍子个数是一样的;

所以不用担心全是0(且f[k]>1的情况),因为那样的话,我们最少会,把第一个数填成一个6;

枚举完第一位之后,剩下的都可以从0开始枚举了;

依次确定每一位即可;



【NumberOf WA】



2



【Reviw】



漏掉了单独一个0的情况了;

没能及时想到状态.



【Code】

/*

    f[i]表示i根棍子能不能组成若干个数字;

    f[b[0..9]] = 1;

    if (f[i])

        dfs(i);

     dfs(int x)

    {

        f[x] = ..

        dfs(x+b[0..9]);

    }

    每个物品可以无限拿,容量为k;

    先取棍子多的数字不一定对.

    可能另外一个棍子小;

    但是两个棍子同样组成了k,但是

    f[i]i根棍子可否组成一个数字,可以的话最少几个数字;

*/

#include <bits/stdc++.h>

#define int long long

using namespace std;

//               0 1 2 3 4 5 6 7 8 9

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

const int c[] = {8,0,6, 9, 2, 3, 5 ,4 ,7 ,1};

const int INF = 0x3f3f3f3f;

//8 0 6 9 2 3 5 4 7 1

const int N = 1e5;

int f[N+10],a[N+10],len;

    int k;

map <int,bool> dic[N+5];

void dfs(int now,int rest){

    if (rest==0) return;

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

    if (rest>=b[j] && f[rest-b[j]] == (f[rest]-1)){

        len++;

        a[now] = j;

        dfs(now+1,rest-b[j]);

        return;

    }

}

main(){

    memset(f,INF,sizeof f);

    f[0] = 0;

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

        if (f[i]<=INF){

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

                int t = i+b[j];

                if (t>N) continue;

                f[t] = min(f[t],f[i]+1);

            }

        }

    scanf("%lld",&k);

    if (f[k]>=INF){

        puts("-1");

    }else{

        if (f[k]==1 && k==b[0]){

            puts("0");

            return 0;

        }

        for (int j = 1;j <= 9;j++)

        {

            if (k-b[j]>=0 && f[k-b[j]] == (f[k]-1)){

                len = 1;

                a[len] = j;

                dfs(2,k-b[j]);

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

                    printf("%lld",a[i]);

                return 0;

            }

        }

        puts("-1");//因为不存在全为0的情况,所以可以去掉这句

    }

    return 0;

}