UVA-12105 Bigger is Better(デジタルdp構想+プリアンブルゼロの判断)

まず、本体の解体構想は劉汝佳が言ったように2つあることを説明しなければならない.
第1に、d(i,j)をi本のマッチで綴った型mの残数jの最大数として定義し、d(i+c(k),(j*10+k)%m)を更新する.(なぜ繰返ししないで更新ブラシ表法を用いるのか、i,jから直接そのサブ状態に移行しようとするため、jの型は計算しにくい)
このアルゴリズムの状態数も移行回数も良いが、大きな数を使わなければならず、タイムアウトする.
第2に、d(i,j)を用いて、iビット数モードmがjのために少なくともどれだけのマッチを必要とするかを示す(特に状態遷移に注意する場合、i>1のときに先頭ゼロがなく、先頭ゼロがあるとお得ではないので、後ろに置くほうがいい).この状態から1つのマッチ数を最大数桁に表すことができる.
ビット数を算出した後、計算する必要があるのは、高位から低位まで順に大きな値を列挙し、m=7とし、最大数を3ビット数とし、例えば1位が9と仮定するとd(2,3)+c(9)<=nとする.第1位は9を置くことができ、順次列挙すれば最大値を得ることができる.ここでのd(i,j)には、プリアンブルゼロがあってもよく、すべて0で構成されていてもよい.(私のやり方は、ゼロdpを押し直すことです)

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 100000
const int maxn = 100 + 5;
const int maxm =  3000 + 50;
const int c[10]={6,2,5,5,4,5,6,3,7,6};
int d[55][maxm],n,m;
int yu[10][55];
int lim = 54,wei,comefrom;
void init(){
  for(int i=1;i<=9;i++) yu[i][1]=i%m;
  for(int i=1;i<=9;i++)
      for(int j=2;j<55;j++)
         yu[i][j]=(yu[i][j-1]*10)%m;
}
int pre_dp(){
  for(int i=0;i<=lim;i++)
          for(int j=0;j<=m;j++)
             d[i][j]=INF;
    for(int i=0;i<=m;i++){
          for(int j=9;j>=1;j--){
               if(j%m==i){
                    if(d[1][i]>c[j]){
                          d[1][i]=c[j];
                    }
               }
          }
    }
    for(int i=1;i<lim;i++)
      for(int j=0;j<=m;j++){
         for(int k=0;k<=9;k++){
         d[i+1][(j*10+k)%m]=min(d[i+1][(j*10+k)%m],d[i][j]+c[k]);
         }
    }
    wei=-1;
    for(int i=lim;i>=1;i--){
          if(d[i][0]<=n){
            wei=i; break;
          }
    }
}
void back_dp(){
   for(int i=0;i<=lim;i++)
          for(int j=0;j<=m;j++)
             d[i][j]=INF;
    for(int i=0;i<=m;i++){
          for(int j=9;j>=0;j--){
               if(j%m==i){
                    if(d[1][i]>c[j]){
                          d[1][i]=c[j];
                    }
               }
          }
    }
    for(int i=1;i<lim;i++)
      for(int j=0;j<=m;j++){
         for(int k=0;k<=9;k++){
         d[i+1][(j*10+k)%m]=min(d[i+1][(j*10+k)%m],d[i][j]+c[k]);
         }
    }
}
void solve(){
    pre_dp();
    if(wei==-1){
          if(n>=6) printf("0
");
          else printf("-1
"); return ;
    }
    back_dp();
    vector<int> ans;
    int temp = n,pre=0;
    for(int i=wei;i>=1;i--){
          for(int j=9;j>=0;j--){
               if(i>1){
               if(c[j]+d[i-1][(m+pre-yu[j][i])%m]<=temp){
                    ans.push_back(j);
                    pre=(m+pre-yu[j][i])%m;
                    temp-=c[j];
                    break;
               }
               }
               else {
                   if(c[j]<=temp&&j%m==pre){
                       ans.push_back(j); break;
                   }
               }
          }
    }
    int all=0,M=0,mi=1;
    for(int i=0;i<ans.size();i++){
        printf("%d",ans[i]);
        all+=c[ans[i]];
        M=(M+ans[i]*mi)%m;
        mi=mi*10%m;
    }  printf("
");
}
int main()
{
    int kase=1;
    while(scanf("%d",&n)==1&&n){
           scanf("%d",&m);
           init();
           printf("Case %d: ",kase++);
           solve();
    }
    return 0;
}