蒙过也是过

(真-暴力枚举) $O(10000)$ 10000=max(N)*num(Ai)

C++ 代码

#include<iostream>
using namespace std;

int N;
int ans[100001] = {1}, s[101];

int main() {
    cin >> N;
    for (int i = 1; i <= N; i++)cin >> s[i];
    for(int i=1;i<=N;i++)
        for (int j = s[i]; j <= 10000; j++)
            if(ans[j]||ans[j - s[i]])ans[j]=1;
    int no1 = 0;
    for (int i = 1; i <= 10000; i++)if (ans[i]==0)no1++;
    if (no1<5000)cout << no1 << endl;
    else cout << "INF" << endl;
    return 0;
}