1226. 包子凑数 - AcWing题库

#include <bits/stdc++.h>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;
}