京东 C++研发 第二题神奇数 AC代码

使用dp实现数组平分功能（http://www.cnblogs.com/maowuyu-xb/p/6433271.html）
然后利用map保存已经计算过的结果，如果已经计算过，直接返回是否为神奇数


#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>

using namespace::std;
//#define debug_
int lef = 0, righ = 0;

bool IsMagical(vector<char>& vec)
{
	int len = vec.size();
	int sum = accumulate(vec.begin(), vec.end(), 0);
	vector<vector<int>> dp(len + 1, vector<int>(sum / 2 + 1));

	for (int i = 1; i <= len; ++i) {
		for (int j = 1; j <= sum / 2; ++j) {
			if (j >= vec[i - 1])dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vec[i - 1]] + vec[i - 1]);
			else dp[i][j] = dp[i - 1][j];
		}
	}
	if ((sum - 2 * dp[len][sum / 2]))
		return false;
	else
		return true;
}

vector<char> getsortnum(int i)
{
	vector<char> vec;
	vec.reserve(10);
	int tmp;
	while (i)
	{
		tmp = i % 10;
		i = i / 10;
		vec.push_back(tmp);
	}
	sort(vec.begin(), vec.end());
	return vec;
}
void func(int lef, int righ)
{
	int count(0);
	bool flag;
	map<vector<char>, bool> my_map;

	for (auto i = lef; i <= righ; ++i)
	{
		vector<char> sorted_num;
		sorted_num.reserve(10);
		int tmp(0), i_tmp(i);
		while (i_tmp)
		{
			tmp = i_tmp % 10;
			i_tmp = i_tmp / 10;
			sorted_num.push_back(tmp);
		}
		sort(sorted_num.begin(), sorted_num.end());

		auto iter = my_map.find(sorted_num);
		if (iter == my_map.end())
		{
			flag = IsMagical(sorted_num);
			my_map[sorted_num] = flag;
			if (flag)
				++count;
		}
		else
		{
			if (iter->second)
				++count;
		}
	}
	cout<< count<<endl;
}

int main()
{
#ifdef debug_
	lef = 1;
	righ = 50;
#else
	cin >> lef;
	cin >> righ;
#endif
	func(lef, righ);
	return 0;
}