PKU 2176 Folding

http://poj.org/problem?id=2176
与えられた文字列の繰り返し等の表示を変更して可能なかぎり圧縮しろというような問題。

メモ化再帰+経路復元。
繰り返し部分は事前計算しました。

こういう問題をとくたびに、経路復元の部分とメモ化再帰の部分がほぼ同一のコードになるので、再利用するようにしようかなとか思いました。

int memo[200][200];
bool vis[200][200];

int repeat[200][200];

int dig(int n){
  int ret=0;
  do{
    n/=10;
    ++ret;
  }while(n);
  return ret;
}

int rec(int s,int e){
  if(e-s<=4)return e-s;
  if(vis[s][e])return memo[s][e];
  vis[s][e]=true;
  int &ret=memo[s][e]=e-s;

  for(int i=s+1;i<e;++i)
    ret=min(ret,rec(s,i)+rec(i,e));

  int len=e-s;
  for(int i=1;i<=len;++i){
    if(len%i)continue;
    if(repeat[s][i+s]+1>=len/i){
      ret=min(ret,dig(len/i)+2+rec(s,s+i));
      //break;
    }
  }
  //cout<<s<<' '<<e<<' '<<ret<<endl;
  return ret;
}

string in;

void getpath(int s,int e,int le){
  if(e-s<=4){
    for(int i=s;i<e;++i)
      cout<<in[i];
    return;
  }

  for(int i=s+1;i<e;++i){
    int fl=rec(s,i);
    int bl=rec(i,e);
    if(fl+bl==le){
      getpath(s,i,fl);
      getpath(i,e,bl);
      return;
    }
  }
  
  int len=e-s;
  for(int i=1;i<=len;++i){
    if(len%i)continue;
    if(repeat[s][i+s]+1>=len/i &&
       dig(len/i)+2+rec(s,s+i)==le){
      cout<<len/i<<'(';
      getpath(s,s+i,rec(s,s+i));
      cout<<')';
      return;
    }
  }
}

main(){
  cin>>in;
  for(int j=SZ(in);j;--j){
    for(int i=0;i<j;++i){
      int le=j-i;
      if(j+le>SZ(in))continue;
      bool ok=true;
      for(int k=0;k<le;++k)
        if(in[i+k]!=in[i+le+k]){
          ok=false;
          break;
        }
      if(ok)repeat[i][j]=repeat[i+le][j+le]+1;
      //cout<<i<<' '<<j<<' '<<repeat[i][j]<<endl;
    }
  }

  //cout<<rec(0,SZ(in))<<endl;

  getpath(0,SZ(in),rec(0,SZ(in)));
  cout<<endl;
}