SRM454 Div1 Medium

500
意外と苦労した。
dp_table[桁数][動かした本数][他の桁へ移った本数]

class NumbersAndMatches {
public:
  long long differentNumbers(long long N, int K) {

    const string num[10][5] = {{"@#@",
                                "# #",
                                "@ @",
                                "# #",
                                "@#@"},
                            
                               {"  @",
                                "  #",
                                "  @",
                                "  #",
                                "@#@"},
                            
                               {"@#@",
                                "  #",
                                "@#@",
                                "#  ",
                                "@#@"},
                            
                               {"@#@",
                                "  #",
                                "@#@",
                                "  #",
                                "@#@"},
                            
                               {"@ @",
                                "# #",
                                "@#@",
                                "  #",
                                "  @"},
                            
                               {"@#@",
                                "#  ",
                                "@#@",
                                "  #",
                                "@#@"},
                            
                               {"@#@",
                                "#  ",
                                "@#@",
                                "# #",
                                "@#@"},
                            
                               {"@#@",
                                "  #",
                                "  #",
                                "  #",
                                "  @"},
                            
                               {"@#@",
                                "# #",
                                "@#@",
                                "# #",
                                "@#@"},
                            
                               {"@#@",
                                "# #",
                                "@#@",
                                "  #",
                                "@#@"}};

    const int M = 10;
    int remove[M][M];
    int add[M][M];

    fill( &remove[0][0], &remove[M-1][M], 0 );
    fill( &add[0][0], &add[M-1][M], 0 );

    for(int i=0; i<M; ++i){
      for(int j=0; j<M; ++j){
        for(int k=0; k<5; ++k){
          for(int l=0; l<3; ++l){
            if( num[i][k][l] == ' ' && num[j][k][l] == '#' ) ++add[i][j];
            if( num[i][k][l] == '#' && num[j][k][l] == ' ' ) ++remove[i][j];
          }
        }
      }
    }

    string s;
    ostringstream oss;
    oss << N;
    s = oss.str();

    static lli t[21][131][260];
    const int base = 130;
    fill( &t[0][0][0], &t[21-1][130-1][260], 0 );

    t[0][0][0 + base] = 1;

    for(int i=0; i<s.size(); ++i){
      for(int j=0; j<=K; ++j){
        for(int k=0; k<260; ++k){
          if( t[i][j][k] == 0 )continue;
          for(int b=0; b<10; ++b){
            int a = s[i] - '0';
            int import = add[a][b] - remove[a][b];
            int move = min( remove[a][b], add[a][b] ) + max( 0, import );
            if( j + move < 131 && 0 <= k + import < 260 && k + import < 260 ){
              t[i + 1][j + move][k + import] += t[i][j][k];
            }
          }
        }
      }
    }

    lli sum = 0;
    for(int i=0; i<=K; ++i){
      sum += t[s.size()][i][0 + base];
    }

    return sum;
  }
};