SRM 655 Div1 easy : LuckySum

問題概要 :
4と7から構成される正の整数をLucky Numberと呼ぶ
[0-9]と?から構成される文字列が与えられる
?には何の数字が入っても良いので、2つのLucky Numberの和がその文字列と等しくなるようなもののうち最小の和を求めよ

解法 :
動的計画法
dp[桁][値][繰り上り][０以外の数字を置いたか][もう０しか置かないか] として解いたけど、0以外の数字を置いたかどうかはいらないような、、、
これは辞書順最小を求めるのに前からDPしてて、それを修正する際に消し忘れただけだと思うけど

状態数少ないし枝刈り探索でも良い気がする

コード :

typedef long long ll;
const int IINF = INT_MAX;
struct PreData {
  int v,carry,bit,bit2;
};

bool dp[20][10][2][4][4];
PreData path[20][10][2][4][4];
int inv[] = {1,2,4,5,7,8,9};
int inc[] = {1,1,0,1,0,1,0};
int nex_v[] = {0,4,7};

class LuckySum {
public:
  string note;
  long long reconstruct(int init_v,int b2){
    if( !dp[0][init_v][0][3][b2] ) return LLONG_MAX;
    PreData cur = (PreData){init_v,0,3,b2};
    string s="";
    s += string(1,(char)('0'+init_v));
    rep(i,(int)note.size()-1){

      PreData &p = path[i][cur.v][cur.carry][cur.bit][cur.bit2];
      s += string(1,(char)('0'+p.v));
      cur.v = p.v;
      cur.carry = p.carry;
      cur.bit = p.bit;
      cur.bit2 = p.bit2;
    }
    stringstream ss;
    ss << s;
    long long ret;
    ss >> ret;
    return ret;
  }

  long long construct( string _note ) {
    note = _note;
    int len = (int)note.size();
    memset(dp,false,sizeof(dp));
    rep(i,20) rep(j,10) rep(k,2) rep(l,4) rep(m,4) path[i][j][k][l][m].v = IINF;

    if( note[len-1] == '?' ) {
      //1 ( = 4 + 7 )
      rep(i,4)dp[len-1][1][1][3][i] = true;

      //4 ( = 7 + 7)
      rep(i,4)dp[len-1][4][1][3][i] = true;
      
      //8
      rep(i,4)dp[len-1][8][0][3][i] = true; // 4 + 4
    } else {
      if( note[len-1] == '1' ) {
        rep(i,4)dp[len-1][1][1][3][i] = true;
      } else if( note[len-1] == '4' ) {
        rep(i,4)dp[len-1][4][1][3][i] = true;
      } else if( note[len-1] == '8' ) {
        rep(i,4)dp[len-1][8][0][3][i] = true; // 4 + 4
      } else return -1;
    }
    
    for(int i=len-1;i>=1;i--){
      vector<int> cand;
      if( note[i-1] == '?' ) {
        rep(j,7) cand.push_back(inv[j]);
      } else {
        cand.push_back(note[i-1]-'0');
      }
      rep(cur_v,10){
        rep(cur_c,2){
          rep(cur_b,4){
            rep(cur_b2,4) {
              if( !dp[i][cur_v][cur_c][cur_b][cur_b2] ) continue;
              rep(j,(int)cand.size()){
                int next_v = cand[j];
                rep(k,3){
                  int nex_v1 = nex_v[k];
                  int nex_b1 = (nex_v1?1:0) | ( cur_b & 1 );
                  if( (cur_b2&1) && nex_v1 ) continue;
                  if( !(cur_b2&1) && nex_v1 == 0 ) continue;
                  
                  rep(l,3){
                    int nex_v2 = nex_v[l];
                    int nex_b2 = ((nex_v2?1:0)<<1) | ( cur_b & 2 );
                    if( ((cur_b2>>1)&1) && nex_v2 ) continue;
                    if( !((cur_b2>>1)&1) && nex_v2 == 0 ) continue;
                    
                    int next_c = ( ( nex_v1 + nex_v2 + cur_c >= 10 ) ? 1 : 0 );
                    
                    if( next_v != (nex_v1+nex_v2+cur_c)%10 ) continue;

                    rep(nex_b21,2) {
                      if( nex_b21 == 0 && ( cur_b2 & 1 ) ) continue;
                      rep(nex_b22,2) {
                        if( nex_b22 == 0 && ( (cur_b2>>1) & 1 ) ) continue;
                        
                        int nex_b_2 = cur_b2 | nex_b21 | (nex_b22<<1);

                        dp[i-1][next_v][next_c][nex_b1|nex_b2][nex_b_2] = true;

                        if( path[i-1][next_v][next_c][nex_b1|nex_b2][nex_b_2].v > cur_v ) {
                          path[i-1][next_v][next_c][nex_b1|nex_b2][nex_b_2].v = cur_v;
                          path[i-1][next_v][next_c][nex_b1|nex_b2][nex_b_2].carry = cur_c;
                          path[i-1][next_v][next_c][nex_b1|nex_b2][nex_b_2].bit = cur_b;
                          path[i-1][next_v][next_c][nex_b1|nex_b2][nex_b_2].bit2 = cur_b2;
                        }

                      }
                    }
                    
                  }
                }
              }
            }
          }
        }
      }
    }
    long long mini = LLONG_MAX;
    rep(i,10) {
      rep(b2,4) {
        mini = min(mini,reconstruct(i,b2));
      }
    }
    if( mini == LLONG_MAX ) return -1;
    return mini;
  }
};