POJ 3340 Barbara Bennett's Wild Numbers

問題

数字と'?'からなる文字列wと数xがマッチするとは、
wのそれぞれの'?'を任意の数字一文字に置き換えたとき、xと一致することを言う。

パターンwと数xが与えられる。
xより大きくwにマッチする数の総数を求めよ。

制約条件

wとxの桁は等しく、かつ10桁以下

方針

典型的な数字DP
dp[i][j]をi桁目まで見て、今まででxより大きくなっていたらj=1そうでなければj=0
であるような数の数であるとする。

このテーブルを更新するような動的計画法により数字の総数が求まる。

ソースコード

char w[20],x[20];
ll n,dp[20][2]; //pos, grater

int main(){
  while(gets(w),w[0]!='#'){
    gets(x);
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    n=strlen(x);
    rep(i,n)rep(greater,2)rep(j,10){
      
      int ngreater=greater||x[i]-'0'<j;
      if(!ngreater&&j<x[i]-'0')continue;
      if(w[i]!='?'&&w[i]-'0'!=j)continue;
      
      dp[i+1][ngreater]+=dp[i][greater];
    }
    printf("%lld\n",dp[n][1]);
  }
  return 0;
}