盗用别人的图片做网站犯法,创建公司主页,广告设计有限公司,可信网站认证是否必须做包子凑数 - 蓝桥云课 (lanqiao.cn)
题目描述 题目分析
对于此题是一个简单DP的翻版问题#xff0c;若能凑出当前的包子数#xff0c;则凑出之前一定为dp[i - a[j]]#xff0c;若表示出的dp[i]不是0则说明是一定存在数可以被凑出的#xff0c;由题意#xff1a;若凑不出的…包子凑数 - 蓝桥云课 (lanqiao.cn)
题目描述 题目分析
对于此题是一个简单DP的翻版问题若能凑出当前的包子数则凑出之前一定为dp[i - a[j]]若表示出的dp[i]不是0则说明是一定存在数可以被凑出的由题意若凑不出的数字超过10000这个上界我们就可以判断出有无穷个
最大不能表示出来的数必定有个上界因为两个数a,b当gcd1时最大不能表示出来的数是a - 1)(b - 1) - 1,题目中的N为10099和98是100内最大的互质的数故这个上界选择10000
#includebits/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;
}
