http://lx.lanqiao.cn/problem.page?gpid=T440
問題描述
小明幾乎每天早晨都會在一家包子鋪吃早餐。他發(fā)現(xiàn)這家包子鋪有N種蒸籠，其中第i種蒸籠恰好能放Ai個包子。每種蒸籠都有非常多籠供填，可以認為是無限籠。
每當有顧客想買X個包子，賣包子的大叔就會迅速選出若干籠包子來兰吟，使得這若干籠中恰好一共有X個包子。比如一共有3種蒸籠茂翔，分別能放3混蔼、4和5個包子。當顧客想買11個包子時珊燎，大叔就會選2籠3個的再加1籠5個的（也可能選出1籠3個的再加2籠4個的）惭嚣。
當然有時包子大叔無論如何也湊不出顧客想買的數(shù)量遵湖。比如一共有3種蒸籠，分別能放4晚吞、5和6個包子延旧。而顧客想買7個包子時，大叔就湊不出來了槽地。
小明想知道一共有多少種數(shù)目是包子大叔湊不出來的迁沫。
輸入格式
第一行包含一個整數(shù)N。(1 <= N <= 100)
以下N行每行包含一個整數(shù)Ai捌蚊。(1 <= Ai <= 100)
輸出格式
一個整數(shù)代表答案集畅。如果湊不出的數(shù)目有無限多個，輸出INF缅糟。
樣例輸入
2
4
5
樣例輸出
6
樣例輸入
2
4
6
樣例輸出
INF
樣例說明
對于樣例1挺智，湊不出的數(shù)目包括：1, 2, 3, 6, 7, 11。
對于樣例2窗宦，所有奇數(shù)都湊不出來赦颇，所以有無限多個。
數(shù)據(jù)規(guī)模和約定
峰值內(nèi)存消耗（含虛擬機） < 256M
CPU消耗 < 1000ms
請嚴格按要求輸出迫摔，不要畫蛇添足地打印類似：“請您輸入...” 的多余內(nèi)容沐扳。
注意：
main函數(shù)需要返回0;
只使用ANSI C/ANSI C++ 標準;
不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。
所有依賴的函數(shù)必須明確地在源文件中 #include <xxx>
不能通過工程設(shè)置而省略常用頭文件句占。
提交程序時沪摄，注意選擇所期望的語言類型和編譯器類型。
這是正解 下面還有個騙分的
refer to
https://blog.csdn.net/qq_34594236/article/details/70803797
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <algorithm>
int N, M;
using namespace std;
const int si =10007;
bool dp[10007];
int arr[107];
int gcd(int a, int b) {
if (b) return gcd(b, a % b);
return a;
}
int main() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", &arr[i]);
}
int g = arr[0];
for (int i = 1; i < N; i++)
g = gcd(g, arr[i]);
if (g != 1) {
printf("INF\n");
return 0;
}
dp[0] = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < si - arr[i]; j++) {
if (dp[j])
dp[j + arr[i]] = 1;
}
}
int ans = 0;
for (int i = 1; i < si; i++)
if (!dp[i]) ans++;
cout << ans << endl;
return 0;
}
騙分 直接當成多重背包做 設(shè)定一個閾值 要是不能搞出來的值多余這個閾值 就認為是INF 否則認為是可行的 測試表明 當閾值為1000時得到75分 3000時87分 5000時得到全分
si = 2e5
總的計算量是2e7 這道題的循環(huán)體很簡單可以大膽些設(shè)置成4e7 然后設(shè)定閾值可以設(shè)大些 更精準
測試表明 si = 4e5, 總的計算量是4e7 閾值=5000時也是100分 跑了16ms
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <algorithm>
int N, M;
using namespace std;
const int si =20007;
bool dp[si];
int arr[107];
int main() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", &arr[i]);
}
dp[0] = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < si - arr[i]; j++) {
if (dp[j])
dp[j + arr[i]] = 1;
}
}
int ans = 0;
for (int i = 1; i < si; i++)
if (!dp[i])
ans++;
if (ans >= 5000)
printf("INF\n");
else
cout << ans << endl;
return 0;
}