京东第2题 神奇数

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<unordered_map>

using namespace std;

int canPartition(unordered_map<string, int>& hash, int k) {
	vector<int> nums;
	string pre;
	int sum = 0;
	while (k > 0) {
		int w = k % 10;
		k /= 10;
		sum += w;
		nums.push_back(w);
		pre += ((w)+'0');
	}
	if (sum & 1) 
		return hash[pre] = 0;
	sort(pre.begin(), pre.end());
	if (hash.find(pre) != hash.end()) 
		return hash[pre];
	sum >>= 1;
	int n = nums.size();
	vector<vector<int>>dp(n, vector<int>(sum + 1, 0));
	for (int i = nums[0]; i <= sum; ++i)
		dp[0][i] = nums[0];
	for (int i = 1; i < n; ++i) 
		for (int j = nums[i]; j <= sum; ++j) 
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
	return hash[pre] = (dp[n - 1][sum] == sum);
}

int main(int argc, char **argv) {
	int l, r;
	unordered_map<string, int> hash;
	while (scanf("%d %d", &l, &r) == 2) {
		int cnt = 0;
		for (int k = l; k <= r; ++k) 
			cnt += canPartition(hash, k);
		printf("%d\n", cnt);
	}
	//cin.get();
	return 0;
}