これもさほど難しくないかな？
http://community.topcoder.com/stat?c=problem_statement&pm=11865
問題
AliceとBobが数字の書かれたカードの山を持っている。
２人がカードの上から順に全部のカードを共有の山に重ねていく。(重ねる順番は１枚ずつ交互でなくてもよい)
また、全部重ね終わったら、また２人が共有の山から自分の山にカードを移していく。（こちらも順番は交互でなくても良い）
AliceとBobの初期のカードの山と、完了後のカードの山が与えられたとき、そのような山を構築できる処理手順の組み合わせを答えよ。
解法
１回共有の山に入れると考えるとややこしいが、最初のAliceまたはBobの山から最後のAliceとBobの山に直接カードを放り込むと考えよう。
状態として[Aliceの初期山残り枚数][Bobの初期山残り枚数][Aliceの完了後山枚数][Bobの完了後山枚数]と４つが考えられるが、全カード枚数はわかっているので３つわかれば残り１つもわかる。
よって以下のコードでは状態を[Aliceの初期山残り枚数][Bobの初期山残り枚数][Aliceの完了後山枚数]で持ち、AliceまたはBobの初期山の一番上のカードを、AliceまたはBobの完了後山に放り込める(数字が一致する)かどうかで判定してDPすればよい。
O(N^3)なので時間は余裕。
ll dp[51][51][51]; ll mo=1000000007; class AliceBobShuffle { public: int countWays(vector <int> AS, vector <int> BS, vector <int> AE, vector <int> BE) { int i,asi,bsi,aei,bei; map<int,int> nc; ITR(it,AS) nc[*it]++; ITR(it,BS) nc[*it]++; ITR(it,AE) nc[*it]--; ITR(it,BE) nc[*it]--; ITR(it,nc) if(it->second) return 0; ZERO(dp); int asl=AS.size(),bsl=BS.size(); int ael=AE.size(),bel=BE.size(),nn=asl+bsl; dp[asl][bsl][0]=1; for(asi=asl;asi>=0;asi--) for(bsi=bsl;bsi>=0;bsi--) { for(aei=0;aei<=ael;aei++) { bei = nn-asi-bsi-aei; if(bei<0 || bei>bel) continue; if(dp[asi][bsi][aei]==0) continue; if(asi>0 && aei<ael && AS[asi-1]==AE[ael-1-aei]) dp[asi-1][bsi][aei+1] = (dp[asi-1][bsi][aei+1] + dp[asi][bsi][aei]) % mo; if(bsi>0 && aei<ael && BS[bsi-1]==AE[ael-1-aei]) dp[asi][bsi-1][aei+1] = (dp[asi][bsi-1][aei+1] + dp[asi][bsi][aei]) % mo; if(asi>0 && bei<bel && AS[asi-1]==BE[bel-1-bei]) dp[asi-1][bsi][aei] = (dp[asi-1][bsi][aei] + dp[asi][bsi][aei]) % mo; if(bsi>0 && bei<bel && BS[bsi-1]==BE[bel-1-bei]) dp[asi][bsi-1][aei] = (dp[asi][bsi-1][aei] + dp[asi][bsi][aei]) % mo; } } return dp[0][0][ael]; } }; *まとめ
