蓝桥杯2017年第八届真题-包子凑数 （C++代码）

解题思路:

注意事项:

参考代码:

#include <stdio.h>
#include <iostream>
#define N 20000

using namespace std;

int a[N];
int n;
bool dp[N];

// TLE的搜索
bool solve_dfs(int res)
{
	if (res == 0) return true;
	else if (res < 0) return false;
	else
	{
		bool ans = false;
		for (int i = 0; i < n; i++)
			if(solve_dfs(res - a[i]))
				ans = true;
		return ans;
	}
}

// 很简单的DP
int solve_dp(int target)
{
	dp[0] = true;
	for (int i = 1; i <= target; i++)
		for (int j = 0; j < n; j++)
			if (i - a[j] >= 0)
				dp[i] |= dp[i - a[j]];

	int ans = 0;
	for (int i = target; i >= 1; i--)
		if (!dp[i])
			ans += 1;
			
	return ans;
}

// 求最大公因数
int gcd(int a, int b)
{
	return (b == 0) ? a : gcd(b, a % b);
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];

	// 判断互质
	int d = a[0];
	for (int i = 1; i < n; i++)
		d = gcd(d, a[i]);
	
	bool rp = (d == 1 ? true : false);

    // 不互质就会有无限个凑不出
	if (!rp)
		cout << "INF";
	else
		cout << solve_dp(10000) << endl; // 只要够暴力

	return 0;
}