工程承包信息_最新新闻热点事件ppt_千锋教育郑州校区_网店推广常用的方法

#include<iostream>
using namespace std;
int gcd(int a,int b) {int tmp;if (a<b) {tmp = a;a = b;b = tmp;}return b == 0 ? a : gcd(b,a%b);
}
int main() {int dp[10001],n;memset(dp,0,sizeof(dp));cin >> n;int* a = new int[n];int g,maxn = 0;for (int i = 0; i < n;i++) {cin >> a[i];if (i == 0) {g = a[i];}else {g = gcd(g,a[i]);}maxn = max(maxn, a[i]);}if (g != 1) {cout << "INF";return 1;}dp[0] = 1;for (int i = 0; i < n;i++) {for (int j = a[i]; j < 10001;j++) {dp[j] = (dp[j]>0||dp[j-a[i]]>0)?1:0;}}for (int i = 10001/2; i>0;i/=2) {int cnt = 0;for (int j = i; j > i - maxn;j--) {if (dp[j] == 1) {cnt++;}}if (cnt != maxn) {int ans = 0;for (int z = 1; z <= i * 2;z++) {if (!dp[z]) {ans++;}}cout << ans;return 0;}}return 0;
}