Bigger is Better

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 1106    Accepted Submission(s): 278

Problem Description

Bob has n matches. He wants to compose numbers using the following scheme (that is, digit 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 needs 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 matches):

Write a program to make a non-negative integer which is a multiple of m. The integer should be as big as possible.

 

 

Input

The input consists of several test cases. Each case is described by two positive integers n (n ≤ 100) and m (m ≤ 3000), as described above. The last test case is followed by a single zero, which should not be processed.

 

 

Output

For each test case, print the case number and the biggest number that can be made. If there is no solution, output -1.Note that Bob don't have to use all his matches.

 

 

Sample Input

6 3 5 6 0

 

 

Sample Output

Case 1: 111 Case 2: -1

 

 

Source

---

题意：要用最多N根火柴摆出一个尽量大的正整数，而且这个数要能够被M整除

洛谷U5033

---

一开始想d[i][j]表示i根火柴模m后为j的最大数字

然后想会溢出

然后想用高精怎么样

然后想高精慢，可以把d[i][j]的值分解成k*m+j，保存k和j就行了，结果并不好转移

然后搜了一下题解

 

用d[i][j]表示i根火柴拼成数字模m后为j有几位

初始化-1不可行，d[0][0]=0

用更新的写法，因为/10总感觉有点悬  

d[i+ms[k]][(j*10+k)%m] 这样dp完了之后再处理每一位是什么，用bit[i][j]表示，n倒着枚举 具体的思想就是，大到小枚举k，找[i][j]第一个能更新到的"合法的"[ti][tj] 对于d[i][j]==mxl，bit[i][j]=10代表这一位最高下面没有了 最后打印方案，从尾开始，因为每次加是加在最后

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int N=105,M=3005,INF=1e9;int n,m;int ms[10]={
    6,2,5,5,4,5,6,3,7,6},d[N][M],bit[N][M];void dp(){    int mxl=0;    memset(d,-1,sizeof(d));    d[0][0]=0;    for(int i=0;i<=n;i++)        for(int j=0;j
           
            =0){ for(int k=0;k<=9;k++) if(i+ms[k]<=n){ if(d[i+ms[k]][(j*10+k)%m]
            
             =0;i--) for(int j=0;j
             
              =0){ if(d[i][j]==mxl&&j==0) {bit[i][j]=10;continue;} for(int k=9;k>=0;k--) if(i+ms[k]<=n){ int ti=i+ms[k],tj=(j*10+k)%m; if(d[ti][tj]==d[i][j]+1&&bit[ti][tj]>=0) {bit[i][j]=k;break;} // if(i==0&&j==0) printf("obit %d %d %d %d\n",ti,tj,d[ti][tj],bit[ti][tj]); } } //printf("hi %d %d %d\n",mxl,d[0][0],bit[0][0]); if(mxl>0){ int i=0,j=0,ti,tj; while(mxl-->0){ ti=i+ms[bit[i][j]]; tj=(j*10+bit[i][j])%m; printf("%d",bit[i][j]); i=ti;j=tj; } }else printf("-1"); printf("\n");}int main(){ int cas=0; while(cin>>n){ if(n==0) break;cin>>m; printf("Case %d: ",++cas); dp(); }}