TopCoder SRM 381 Div1 Medium TheHomework

問題

数列firstに、以下の操作を繰り返してsecondにしたい。
（数の順番は一致してなくともよい）

• add 任意の数を加える。加える数の個数は元の数列の項数を超えてはならない
• delete 数を消す。消す数の個数は元の数列の項数の半分を超えてはならない
• change 数を変更する。変更する数の個数は元の数列の項数の半分を超えてはならない。

必要な操作の回数の最小値を求めよ。

制約条件

firstの要素数≦50
secondの要素数≦50
first[i],second[i]≦1000

方針

(一致している項の数、一致してない項の数）を状態とするメモ化再帰。
項の数が200を超えたら明らかに打ち切っていいので打ち切る。

循環したらINFになっているので単純に再帰して上手く行く。

Editorialの解法ではこれを幅優先探索で行っていた。

ソースコード

int m,dp[200][200];//一致、不一致
int rec(int a,int b){
  if(a>=200||b>=200||a<0||b<0)return inf;
  if(dp[a][b]>=0)return dp[a][b];
  if(a==m&&b==0)return 0;
  int &res=dp[a][b];
  res=inf;
  int n=a+b;
  rep(i,min(n/2,b))res=min(res,1+rec(a+i+1,b-i-1));
  rep(i,n)res=min(res,1+rec(a+i+1,b));
  rep(i,min(n/2,b))res=min(res,1+rec(a,b-i-1));
  return res;
}
class TheHomework {
  public:
  int transform(vector <int> first, vector <int> second) {
    rep(i,200)rep(j,200)dp[i][j]=-1;
    int n=first.size();
    m=second.size();
    int a=0,b=0;
    rep(i,n){
      rep(j,second.size())if(first[i]==second[j]){
        a++;
        second.erase(second.begin()+j); goto NEXT;
      }
      b++;
      NEXT:;
    }
    return rec(a,b);
  }
};