这题目有点难，关键是dp状态的选择不好想，在实现上用了 C++ STL中的set 和 map，效率不是很高，可以考虑用 bitmask 提高效率。
代码如下：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /*************** Program Begin **********************/ typedef set seti; const int MOD = 1000000007; class AlienAndSetDiv2 { public: int N, K; map dp[105]; int calc(int n, seti unmatched) { int res = 0; map ::iterator it; it = dp[n].find(unmatched); if (it != dp[n].end()) { return dp[n][unmatched] % MOD; } if (n == 2 * N + 1) { if (unmatched.size() == 0) { res = 1; } } else { seti newset; if (unmatched.size() == 0) { newset = unmatched; newset.insert(n); res += ( 2 * calc(n+1, newset) ) % MOD; } else { newset = unmatched; int m = *newset.begin(); newset.erase(newset.begin()); res += calc(n+1, newset); res %= MOD; if (m != n - K) { newset = unmatched; newset.insert(n); res += calc(n+1, newset); res %= MOD; } } } dp[n][unmatched] = res; return res; } int getNumber(int N, int K) { this->N = N; this->K = K; int res = 0; seti unmatched; res = calc(1, unmatched); return res; } }; /************** Program End ************************/