蓝桥杯每日一题2023.11.9
包子凑数 - 蓝桥云课 (lanqiao.cn)
题目描述
题目分析
对于此题是一个简单DP的翻版问题，若能凑出当前的包子数，则凑出之前一定为dp[i - a[j]]，若表示出的dp[i]不是0则说明是一定存在数可以被凑出的，由题意：若凑不出的数字超过10000这个上界，我们就可以判断出有无穷个
最大不能表示出来的数必定有个上界，因为两个数a,b（当gcd=1时），最大不能表示出来的数是（a - 1)(b - 1) - 1,题目中的N为100，99和98是100内最大的互质的数，故这个上界选择10000
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7;
int a[N], dp[N];
int main()
{int n, ans = 0;cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];dp[a[i]] ++;}for(int i = 1; i <= N; i ++){for(int j = 1; j <= n; j ++){if(i - a[j] < 0)continue;dp[i] = dp[i - a[j]] + dp[i];if(dp[i] != 0)break;//这个数可以被凑出 }if(dp[i] == 0)ans ++;}if(ans > 10000)cout << "INF";else cout << ans;return 0;
}