京东笔试--神奇数
我来抛砖引玉一个，对每个数判断是否是神奇数，用01背包问题的思路解的。
没想到这么暴力都能AC
bool IsNum(int num){
vector<int> arr;
int all(0);
while (num){
all += num % 10;
arr.push_back(num % 10);
num = num / 10;
}
if (all % 2){
return false;
}
int half = all / 2;
vector<int> dp(half + 1);
for (int i = 0; i < arr.size(); i++){
int cap(half);
while (cap >= arr[i]){
dp[cap] = max(dp[cap - arr[i]] + arr[i], dp[cap]);
cap--;
}
}
return dp[half] == half;
}
int main(){
int l(0), r(0);
cin >> l >> r;
int res(0);
for (int i = l; i <= r; i++){
if (IsNum(i)){
res++;
}
}
cout << res;
return 0;
}
#京东##C++工程师#
投递美团等公司8个岗位
