题目:http://community.topcoder.com/stat?c=problem_statement&pm=12891&rd=15713
参考:http://apps.topcoder.com/wiki/display/tc/SRM+601
先尝试简单dp方法,时间复杂度O( max(N, M)^3 ),此方法只能求解 max(N, M)不超过200的情况,如下:
#include <algorithm> #include <functional> #include <numeric> #include <utility> #include <iostream> #include <sstream> #include <iomanip> #include <bitset> #include <string> #include <vector> #include <stack> #include <deque> #include <queue> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cctype> #include <cmath> #include <cstring> #include <ctime> #include <climits> using namespace std; #define CHECKTIME() printf("%.2lf\n", (double)clock() / CLOCKS_PER_SEC) typedef pair<int, int> pii; typedef long long llong; typedef pair<llong, llong> pll; #define mkp make_pair /*************** Program Begin **********************/ const int MOD = 1e9 + 7; int dp[200][200][200]; class WinterAndSnowmen { public: int N, M; int rec(int t, int x, int y) { if (t == 0) { if (x < y) { return 1; } else { return 0; } } int & res = dp[t][x][y]; if (res != -1) { return res; } res = 0; if (t <= N) { res += rec(t - 1, x ^ t, y); res %= MOD; } if (t <= M) { res += rec(t - 1, x, y ^ t); res %= MOD; } res += rec(t - 1, x, y); res %= MOD; return res; } int getNumber(int N, int M) { this->N = N; this->M = M; memset(dp, -1, sizeof(dp)); return rec(max(N, M), 0, 0); } }; /************** Program End ************************/
按 Editorials 中给的方法进行优化,得到O( max(N, M) ^ 2 ),最后的optimizations一定也要做,要不然还是会超时,如下:
#include <algorithm> #include <functional> #include <numeric> #include <utility> #include <iostream> #include <sstream> #include <iomanip> #include <bitset> #include <string> #include <vector> #include <stack> #include <deque> #include <queue> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cctype> #include <cmath> #include <cstring> #include <ctime> #include <climits> using namespace std; #define CHECKTIME() printf("%.2lf\n", (double)clock() / CLOCKS_PER_SEC) typedef pair<int, int> pii; typedef long long llong; typedef pair<llong, llong> pll; #define mkp make_pair /*************** Program Begin **********************/ const int MOD = 1e9 + 7; const int MAX_BITS = 11; const int MAX_N = 2000; int dp[MAX_N + 1][1 << MAX_BITS][2]; class WinterAndSnowmen { public: int p, N, M; inline int getBit(int z, int p) { return ( (z >> p) & 1 ); } int rec(int t, int z, int b) { if (0 == t) { if ( 0 == b && 1 == z ) { return 1; } else { return 0; } } int & res = dp[t][z][b]; if (res != -1) { return res; } res = 0; if (t <= N) { res += rec(t - 1, z ^ (t >> p), b ^ getBit(t, p)); res %= MOD; } if (t <= M) { res += rec(t - 1, z ^ (t >> p), b); res %= MOD; } res += rec(t - 1, z, b); res %= MOD; return res; } int getNumber(int N, int M) { this->N = N; this->M = M; int res = 0; for (p = 0; p < 11; p++) { memset(dp, -1, sizeof(dp)); res += rec( max(N, M), 0, 0 ); res %= MOD; } return res; } }; /************** Program End ************************/