一:題目

題目描述
小明幾乎每天早晨都會(huì)在一家包子鋪吃早餐。他發(fā)現(xiàn)這家包子鋪有 NN 種蒸籠，其中第 ii 種蒸籠恰好能放 A_iA
i
?
個(gè)包子。每種蒸籠都有非常多籠，可以認(rèn)為是無限籠。

每當(dāng)有顧客想買 XX 個(gè)包子，賣包子的大叔就會(huì)迅速選出若干籠包子來，使得這若干籠中恰好一共有 XX 個(gè)包子。比如一共有 3 種蒸籠，分別能放 3、4 和 5 個(gè)包子。當(dāng)顧客想買 11 個(gè)包子時(shí)，大叔就會(huì)選 2 籠 3 個(gè)的再加 1 籠 5 個(gè)的（也可能選出 1 籠 3 個(gè)的再加 2 籠 4 個(gè)的）。

當(dāng)然有時(shí)包子大叔無論如何也湊不出顧客想買的數(shù)量。比如一共有 3 種蒸籠，分別能放 4、5 和 6 個(gè)包子。而顧客想買 7 個(gè)包子時(shí)，大叔就湊不出來了。

小明想知道一共有多少種數(shù)目是包子大叔湊不出來的。

輸入描述
第一行包含一個(gè)整數(shù) NN (1 \leq N \leq 1001≤N≤100)。

以下 N 行每行包含一個(gè)整數(shù) A_iA
i
?
(1 \leq A_i \leq 1001≤A
i
?
≤100)。

輸出描述
一個(gè)整數(shù)代表答案。如果湊不出的數(shù)目有無限多個(gè)，輸出 INF。

輸入輸出樣例 示例 1 輸入2 4 5 copy 輸出6 copy 樣例說明湊不出的數(shù)目包括：1, 2, 3, 6, 7, 11。示例 2 輸入2 4 6 copy 輸出INF copy

樣例說明

所有奇數(shù)都湊不出來，所以有無限多個(gè)

二:上碼

/**思路:1.分析題意 題目給出了幾個(gè)數(shù)找出這幾個(gè)數(shù)目湊不出來的數(shù)有幾個(gè)2.動(dòng)態(tài)規(guī)劃1>:確定dp是什么,以及下標(biāo)是什么dp[j]表示的是包子個(gè)數(shù)是j, 是否可以被籠子里的包子的個(gè)數(shù)湊出 2>:確定dp的遞推公式是什么 dp[j] = dp[j]; dp[j] = dp[j - nums[i]];//其中nums[i]表示的是籠子里的包子個(gè)數(shù) //j就是表示出的是我們的可以湊出的包子個(gè)數(shù) 3>:初始化初始化為false; 4>:確定遍歷順序外層遍歷物品（也就是給出的籠子里的包子個(gè)數(shù)）里層遍歷物品重量（也就是我們可以湊出包子的個(gè)數(shù)）for (int i = 1; i <= N; i++) {for (int j = nums[i]; j <= M; j++) {//這里從j = nums[i]開始，是怕出現(xiàn)負(fù)數(shù) dp[j] = dp[j-nums[i]; }}5>:模擬 */#include<bits/stdc++.h> using namespace std;int main() {int N;vector<bool>dp(10005,0);int count1 = 0;int count2 = 0;cin >> N;vector<int> nums(N);for (int i = 0; i < N; i++) {cin >> nums[i];if(i == 0) {count1 = nums[i];}else{count1 = __gcd(count1,nums[i]);//求取最大公約數(shù),如果最終求出的公約數(shù)大于1,說明不互質(zhì)}} // 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++) {//遍歷物品 也就是我們包子的個(gè)數(shù) dp[j] = dp[j-nums[i]] | dp[j]; // cout << dp[j] << ' ';} // cout << endl;} // for (int j = 1; j <= 10; j++) {//遍歷物品 也就是我們包子的個(gè)數(shù) // cout << dp[j] << " "; // } for(int i = 1; i <= 10005; i++) {if(dp[i] == 0) count2++;}cout << count2; }

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯- 包子凑数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。