西安网站建设昆奇,网络管理网站策划书,网站推广的目标是什么,高速访问免费全自动网页制作系统一:题目
题目描述 小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 NN 种蒸笼#xff0c;其中第 ii 种蒸笼恰好能放 A_iA i 个包子。每种蒸笼都有非常多笼#xff0c;可以认为是无限笼。
每当有顾客想买 XX 个包子#xff0c;卖包子的大叔就会迅速选出若…一:题目
题目描述 小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 NN 种蒸笼其中第 ii 种蒸笼恰好能放 A_iA i 个包子。每种蒸笼都有非常多笼可以认为是无限笼。
每当有顾客想买 XX 个包子卖包子的大叔就会迅速选出若干笼包子来使得这若干笼中恰好一共有 XX 个包子。比如一共有 3 种蒸笼分别能放 3、4 和 5 个包子。当顾客想买 11 个包子时大叔就会选 2 笼 3 个的再加 1 笼 5 个的也可能选出 1 笼 3 个的再加 2 笼 4 个的。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3 种蒸笼分别能放 4、5 和 6 个包子。而顾客想买 7 个包子时大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入描述 第一行包含一个整数 NN (1 \leq N \leq 1001≤N≤100)。
以下 N 行每行包含一个整数 A_iA i (1 \leq A_i \leq 1001≤A i ≤100)。
输出描述 一个整数代表答案。如果凑不出的数目有无限多个输出 INF。
输入输出样例
示例 1
输入2
4
5
copy
输出6
copy
样例说明凑不出的数目包括1, 2, 3, 6, 7, 11。示例 2
输入2
4
6
copy
输出INF
copy样例说明
所有奇数都凑不出来所以有无限多个
二:上码
/**思路:1.分析题意 题目给出了几个数找出这几个数目凑不出来的数有几个2.动态规划1:确定dp是什么,以及下标是什么dp[j]表示的是包子个数是j, 是否可以被笼子里的包子的个数凑出 2:确定dp的递推公式是什么 dp[j] dp[j]; dp[j] dp[j - nums[i]];//其中nums[i]表示的是笼子里的包子个数 //j就是表示出的是我们的可以凑出的包子个数 3:初始化初始化为false; 4:确定遍历顺序外层遍历物品也就是给出的笼子里的包子个数里层遍历物品重量也就是我们可以凑出包子的个数for (int i 1; i N; i) {for (int j nums[i]; j M; j) {//这里从j nums[i]开始是怕出现负数 dp[j] dp[j-nums[i]; }}5:模拟 */#includebits/stdc.h
using namespace std;int main() {int N;vectorbooldp(10005,0);int count1 0;int count2 0;cin N;vectorint nums(N);for (int i 0; i N; i) {cin nums[i];if(i 0) {count1 nums[i];}else{count1 __gcd(count1,nums[i]);//求取最大公约数,如果最终求出的公约数大于1,说明不互质}} // cout count1 wyj;if(count1 1) {cout INF; return 0;}dp[0] 1;for (int i 0; i N; i) {//遍历背包 for (int j nums[i]; j 10005; j) {//遍历物品 也就是我们包子的个数 dp[j] dp[j-nums[i]] | dp[j];
// cout dp[j] ;}
// cout endl;} // for (int j 1; j 10; j) {//遍历物品 也就是我们包子的个数
// cout dp[j] ;
// } for(int i 1; i 10005; i) {if(dp[i] 0) count2;}cout count2;
}
