COIN34 - 34 đồng xu

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<map>
using namespace std;

#define TR(v,i) for(typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int MAX = 2000000000;
long long sum;
map<int, int> map1, map2;
int coin[34];

void maximize(int &a, const int &b) { if(a < b) a = b; }
void backtrack(int begin, int end, long long sum, int c, map<int, int> &m) {
	if(sum > MAX) return;
	if(begin == end) maximize(m[sum], c);
	else {
		backtrack(begin+1, end, sum, c, m);
		backtrack(begin+1, end, sum+coin[begin], c+1, m);
	}
}

int main() {
	coin[0] = 2; coin[1] = 3; coin[2] = 5;
	for(int i = 3; i < 34; ++i) coin[i] = coin[i-1] + coin[i-2] + coin[i-3];
	backtrack(0, 17, 0, 0, map1);
	backtrack(17, 34, 0, 0, map2);
	int T; scanf("%d", &T);
	for(int t = 1; t <= T; ++t) {
		int x, res = -1; scanf("%d", &x);
		TR(map2, it) if(it->first <= x) {
			if(map1.count(x - it->first))
				maximize(res, it->second + map1[x - it->first]);
		} else break;
		printf("Case #%d: %d\n", t, res);
	}
	return 0;
}

Download