題目描述：

小明幾乎每天早晨都會(huì)在一家包子鋪吃早餐。

他發(fā)現(xiàn)這家包子鋪有?N?種蒸籠，其中第?i?種蒸籠恰好能放?Ai 個(gè)包子。

每種蒸籠都有非常多籠，可以認(rèn)為是無(wú)限籠。

每當(dāng)有顧客想買(mǎi)?X?個(gè)包子，賣(mài)包子的大叔就會(huì)迅速選出若干籠包子來(lái)，使得這若干籠中恰好一共有?X?個(gè)包子。

比如一共有?3?種蒸籠，分別能放?3、4和?5?個(gè)包子。

當(dāng)顧客想買(mǎi)?11個(gè)包子時(shí)，大叔就會(huì)選?2?籠?3?個(gè)的再加?1?籠?5?個(gè)的（也可能選出?1?籠?3?個(gè)的再加?2?籠?4?個(gè)的）。

當(dāng)然有時(shí)包子大叔無(wú)論如何也湊不出顧客想買(mǎi)的數(shù)量。

比如一共有?3?種蒸籠，分別能放?4、5和?6?個(gè)包子。

而顧客想買(mǎi)?7?個(gè)包子時(shí)，大叔就湊不出來(lái)了。

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

輸入格式:

第一行包含一個(gè)整數(shù)?N。

接下來(lái)?N?行，每行包含一個(gè)整數(shù)?Ai。

輸出格式:

輸出一個(gè)整數(shù)代表答案。

如果湊不出的數(shù)目有無(wú)限多個(gè)，輸出INF。

數(shù)據(jù)范圍:

1≤N≤100,
1≤Ai≤100

輸入樣例1：

2
4
5

輸出樣例1：

6

輸入樣例2：

2
4
6

輸出樣例2：

INF

樣例解釋

對(duì)于樣例1，湊不出的數(shù)目包括：1, 2, 3, 6, 7, 11。
對(duì)于樣例2，所有奇數(shù)都湊不出來(lái)，所以有無(wú)限多個(gè)。

前情提要：這道題目有關(guān)完全背包，01背包這兩道題目，如果沒(méi)看過(guò)這兩道題目的題解大家可以去看看，能幫助理解這道題目。鏈接我也放到這里了，點(diǎn)擊鏈接就行。

分析步驟：

? 第一：看到題目我們就能明白，每一籠包子是可以選無(wú)數(shù)多籠的，只要次數(shù)不超過(guò)我們指定的個(gè)數(shù)，看看能組合出多少種組合來(lái)，最后判斷一下有多少個(gè)數(shù)組合出來(lái)了，多少個(gè)數(shù)沒(méi)有組合出來(lái)那么這就是答案。由此可以得出第一個(gè)特點(diǎn)：題目是?組合問(wèn)題，是完全背包問(wèn)題的變形：有幾個(gè)物品，每個(gè)物品無(wú)限個(gè)，每個(gè)物品選任意個(gè)，能否湊到某個(gè)重量。

? 第二：我們?nèi)绾?span style="color:#fe2c24;">判斷這個(gè)題目是否有無(wú)數(shù)個(gè)值會(huì)組合不出來(lái)呢？我們想一下什么樣的就組合不出來(lái)，例如2，4，6最大公約數(shù)是2所以奇數(shù)組合不出來(lái)，因?yàn)樗荒芙M合出gcd的倍數(shù)。例如30，60最大公約數(shù)是30，所以只要不是30的倍數(shù)的就一定組合不出來(lái)，由此我們可以發(fā)現(xiàn)一些問(wèn)題組合數(shù)和gcd有關(guān)，只要gcd不是1的話(huà)那么它就有無(wú)數(shù)種數(shù)組合不出來(lái)。這里用到裴蜀定理 ，任意兩個(gè)數(shù)的組合必定是他們gcd的倍數(shù)，同樣可以推廣到更多數(shù)：如果這些數(shù)的gcd的d不是1那么有無(wú)數(shù)個(gè)數(shù)組合不出來(lái)

? 第三：閆氏DP分析法：

• 根據(jù)閆氏DP分析法我們可以知道dp問(wèn)題可以將其分解為兩個(gè)步驟：第一種是狀態(tài)表示，第二種是狀態(tài)計(jì)算。

• 我們所有的背包問(wèn)題都是圍繞我們對(duì)于集合的定義來(lái)的，所以這個(gè)定義是非常重要的！！！我們將集合定義為：所有只從前i個(gè)包子中選擇，數(shù)量為j的集合是否能夠達(dá)到題目要求的包子數(shù)，是個(gè)bool數(shù)組。

• 狀態(tài)計(jì)算：由于完全背包是可以無(wú)限次的選擇物品的，所以我們不能和01背包一樣，只將其分解為選或者不選，因?yàn)樗梢杂泻芏嗪芏喾N選擇，可以不選，可以選一種，可以選兩種...只要題目要求包子數(shù)量（背包體積）足夠大就可以。

• 如果他不選擇包子?i?那么這種情況相當(dāng)于從（1，i - 1）中選擇數(shù)量不超過(guò)j的情況是一樣的所以我們的表達(dá)式是：f[i-1][j]。

• 如果他選擇物品 i 那么這樣又該如何表示呢？我們并不知道他到底要選擇幾個(gè)物品，那應(yīng)該怎么做呢？假如我們選擇一個(gè)的話(huà)那么就應(yīng)該寫(xiě)為f[i-1][j-vi];假如我們選擇兩個(gè)的話(huà)那么就應(yīng)該寫(xiě)為f[i-1][j-2*vi];假如我們選擇k個(gè)的話(huà)那么就應(yīng)該寫(xiě)為f[i-1][j-k*vi]，那么我們最終的答案就應(yīng)該在這些集合之中。

• 

• 所以f(i,j) ?= f(i-1 , j) ||?f(i-1 , j - v) ||?f(i-1 , j - 2v) ||?........|| f(i-1 , j - (j/v)*v);

• 所以f(i,j-v) = f(i-1 , j - v) ||?f(i-1 , j - 2*v) ||?f(i-1 , 3*v) ||?........f(i-1 , j - (j/v)*v);

• 由上述兩個(gè)式子，我們可以知道如果將 j 替換成 j-vi 兩個(gè)式子非常相似。f[ i ] [ j ] = f[ i -1][ j ] ||?f[ i ][ j - vi ] ;

? 第四：書(shū)寫(xiě)主函數(shù)，構(gòu)建整體框架：

1. 輸入值，并且根據(jù)裴蜀定理求出最大公約數(shù)看看是不是1，如果不是1那么必定有無(wú)數(shù)個(gè)值組合不出來(lái)，那么直接輸出INF。初始化一下我們的f數(shù)組全部賦值為0，初始化我們的f[0][0] = true。為什么？根據(jù)我們對(duì)集合的定義來(lái)分析：只從前i個(gè)包子中選擇，數(shù)量為j的集合是否能夠達(dá)到題目要求的包子數(shù)。那么f[0][0]代表前0個(gè)包子中選擇，數(shù)量為0的集合是可能的所以初始化為true。

   for(int i = 1 ; i <= n ; ++ i){for(int j = 0 ; j <= 10000 ; ++ j){f[i][j] = f[i-1][j] || (j >= arr[i] ? f[i][j - arr[i]] : false) ;}}

2. d==1 的話(huà)我們就進(jìn)入雙重for循環(huán)。第一個(gè)for就是包子種類(lèi)，第二個(gè)for就是包子數(shù)量。那么問(wèn)題來(lái)了。我們?cè)趺创_定數(shù)量最大值就是10000呢？那么當(dāng)qcd為1時(shí)，最大不能表示出來(lái)的數(shù)必定有個(gè)上界，因?yàn)閮蓚€(gè)數(shù)a，b(當(dāng)gcd=1時(shí))，最大不能表示出數(shù)是：(a-1)(b-1)-1。當(dāng)數(shù)字更多的時(shí)候，這個(gè)上界必然更小(可選的數(shù)字變多了)，而99和98是100內(nèi)最大的互質(zhì)的數(shù)，所以這個(gè)上界選擇10000。

3. 我們之前分析出了f[ i ] [ j ] = f[ i -1][ j ] ||?f[ i ][ j - vi ] ;但是注意一個(gè)問(wèn)題：選擇一個(gè)，選擇兩個(gè)，是在所需包子數(shù)大于我們的這一籠包子數(shù)的情況下才可以選，假如所需包子數(shù)都要小于這一籠包子數(shù)的話(huà)就不可以選了！所以我們選擇了用三目運(yùn)算符?(j >= arr[i] ? f[i][j - arr[i]] : false) ;這句話(huà)的意思是如果 j >= arr[i] 是對(duì)的話(huà)那么則返回f[i][j - arr[i]] ；如果不對(duì)則返回false，那么f[ i ] [ j ] = f[ i -1][ j ] ||?f[ i ][ j - vi ]這就是錯(cuò)了就代表組合不出這個(gè)數(shù)。

4. 最后我們只需要在遍歷一遍，看看哪些數(shù)是組合不出來(lái)的，組合不出來(lái)就res++。

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110 ;int n ; 
bool f[N][10010];
int arr[N];int gcd(int a , int b){return b ? gcd(b,a%b):a;
}int main()
{cin>>n;int d = 0;for(int i = 1 ; i <= n ; ++i){cin>>arr[i];d = gcd(d,arr[i]);}memset(f, 0, sizeof f);f[0][0] = true;if(d != 1) cout<<"INF"<<endl;else{for(int i = 1 ; i <= n ; ++ i){for(int j = 0 ; j <= 10000 ; ++ j){f[i][j] = f[i-1][j] || (j >= arr[i] ? f[i][j - arr[i]] : false) ;}}int res = 0;for(int i = 0 ; i <= 10000 ; i ++){if(!f[n][i]) res ++;}cout<<res;
}return 0;
}

01背包從后往前，完全背包從前往后！！