蓝桥杯刷题-包子凑数

1226. 包子凑数 - AcWing题库

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