SRM416 div2 hard
十八番のメモ化再帰。
#include <algorithm> #include <cstring> #include <string> #include <vector> using namespace std; class DancingCouples { public: vector <string> can; int bn,gn; int cache[11][11][(1<<10)]; int rec(int b,int K,int left) { int &r=cache[b][K][left]; if(r!=-1) return r; if(K==0) return r=1; if(b==bn) return r=0; r=0; r+=rec(b+1,K,left); for(int g=0;g<gn;g++) if((left&(1<<g)) && can[b][g]=='Y') r+=rec(b+1,K-1,left&(~(1<<g))); return r; } int countPairs(vector<string> _canDance,int K) { can=_canDance; bn=can.size(),gn=can[0].size(); memset(cache,-1,sizeof(cache)); return rec(0,K,(1<<gn)-1); } };