PKU 3516 Johnny Hates Math

http://poj.org/problem?id=3516
数字=数字という式の左辺に+を入れて等式が成り立つようにしろというような問題。
ただし、数字は全て正数で最上位桁は0でない。
また、候補が複数ある場合は+の個数が最小になるものを出力すること。

＋の個数の条件を見落としていてWAの原因に頭を悩ませました。
setだと無理っぽかったのでハッシュ使いました。
DP+経路復元っぽい問題でした。

string in;

typedef struct _node{
  int a,b;
  int c;
  _node* next;
}node;

const int hashMod=300000;
node* hash[hashMod];
node ent[10000000];
int sz;

void insert(int a,int b,int c){
  int ha=(a*31+b)%hashMod;
  node* p=ent+sz++;
  p->a=a;
  p->b=b;
  p->c=c;
  p->next=hash[ha];
  hash[ha]=p;

}

node* app(int a,int b){
  int ha=(a*31+b)%hashMod;
  for(node* p=hash[ha];p;p=p->next)
    if(p->a==a && p->b==b)return p;
  return NULL;
}

int  rec(int p,int nu){
  if(p==0 && nu==0)return 0;
  if(nu<=0)return -1;
  {
    node* re=app(p,nu);
    if(re)return re->c;
  }
  int ret=-1;

  int base=1;
  int re=0;
  for(int i=0;i<5;++i){
    if(p-i-1<0)break;
    re+=base*(in[p-i-1]-'0');
    base*=10;
    if(in[p-i-1]=='0')continue;
    int tre=rec(p-i-1,nu-re);
    if(tre>=0){
      if(ret==-1)ret=tre+1;
      ret=min(ret,tre+1);
    }
  }
  insert(p,nu,ret);
  return ret;  
}


void getpath(int p,int nu){
  if(p==0 && nu==0)return;
  int base=1;
  int re=0;
  int ret=app(p,nu)->c;
  for(int i=0;i<5;++i){
    re+=base*(in[p-i-1]-'0');
    base*=10;
    if(in[p-i-1]=='0')continue;
    if(rec(p-i-1,nu-re)+1==ret){
      getpath(p-i-1,nu-re);
      if(nu-re)
        cout<<'+';
      cout<<re;
      return;
    }
  }
}

void solve(int n){
  printf("%d. ",n);
  memset(hash,0,sizeof(hash));
  sz=0;
  int re=0;
  for(int i=in.find('=')+1;i<SZ(in);++i)
    re=re*10+in[i]-'0';

  if(rec(in.find('='),re)>=0){
    getpath(in.find('='),re);
    cout<<in.substr(in.find('='))<<endl;
  }else puts("IMPOSSIBLE");
}

main(){
  int te=0;
  while(cin>>in,in!="0=0")
    solve(++te);
}