SRM 612 D2L3：PowersOfTwo.htm，dp

题目：http://community.topcoder.com/stat?c=problem_statement&pm=13042&rd=15845

参考：http://apps.topcoder.com/wiki/display/tc/SRM+612

典型的dp，将问题划分为相同的子问题。

代码：

#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 **********************/
long long dp[65][55];
vector <long long> X(60);
class PowersOfTwo {
public:
	long long rec(int k, int b)
	{
		long long & res = dp[k][b];
		if (res != -1) {
			return res;
		}
		// base case
		if (k == X.size()) {
			res = 1;
			return res;
		}
		res = 0;
		int x_k = X[k] + b;
		res += rec(k + 1, x_k / 2);
		if (x_k > 0) {
			res += rec(k + 1, (x_k - 1) / 2);
		}

		return res;
	}
	long long count(vector <long long> powers) {
		long long res = 0LL;
		memset(dp, -1, sizeof(dp));
		for (int i = 0; i < X.size(); i++) {
			X[i] = std::count(powers.begin(), powers.end(), 1LL << i);
		}
		res = rec(0, 0);
		return res;
	}

};

/************** Program End ************************/

SRM 612 D2L3：PowersOfTwo.htm，dp,古老的榕树,5-wow.com