完全背包秒了

#include<iostream>
#include<cstdio>
#include<bitset>

using namespace std;

inline long long read(){
	long long x=0,f=1; char c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}

int n,m=10000000,a[20],tmp;
bool f[10000007];

long long gcd(long long a,long long b){
	if (b==0) return a;
	return gcd(b,a%b);
}

int main(){
//	freopen("A.in","r",stdin);
	n=read(); if (n==1){printf("0"); return 0;}
	for (int i=1;i<=n;i++){
		a[i]=read();
		f[a[i]]=1;
	}
	tmp=a[1];
	for (int i=2;i<=n;i++){
		tmp=gcd(tmp,a[i]);
	}
	if (tmp!=1){printf("0"); return 0;}
	
	for (int i=1;i<=n;i++){//可以取无限次的背包 
		for (int j=a[i];j<=m;j++){
			f[j]|=f[j-a[i]];
		}
	}
	for (int i=m;i>=0;i--){
		if (!f[i]){
			printf("%d",i);
			return 0;
		}
	}
	return 0;
}

我们直接考虑乱搞做法

因为我们不知道答案的上限（其实可以算，因为我太唐了不会算）我们直接不停的向上算，直到时间快到了就退出，输出我们目前可以获得的最大的答案

我们设 $mp_i$ 表示 $i$ 这个数可不可以被表示出来，那么则有：

判断一下无解：如果所有 $a_i$ 的gcd大于 $0$ ，那么就输出无解

但是我们要注意，评测机太快了，我们得把时间开大，详见这里

#include<iostream>
#include<cstdio>
#include<time.h>
#include<map>
#define int long long
#pragma GCC optimize(2)
using namespace std;
bool Test_MLE_start;
int T=1,n,ans=-2e9;
int a[15];
map<int,bool> mp;
double strt,nd;
inline int reads(){
	char c=getchar();
	int sum=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		sum=(sum<<3)+(sum<<1)+(c^'0');
		c=getchar();
	}
	return sum*f;
}
inline void files(){
	freopen("A.in","r",stdin);
//	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
int gcd(int n,int m){
	return m?gcd(m,n%m):n; 
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	T=reads();
	strt=clock();
	while(T--){
		clr();
		n=reads();
		for(int i=1;i<=n;i++){
			a[i]=reads();
			mp[a[i]]=1;
			if(a[i]==1){
				puts("0");
				return 0;
			}
		}
		int GCD=a[1];
		for(int i=2;i<=n;i++) GCD=gcd(GCD,a[i]);
		if(GCD!=1){
			puts("0");
			return 0;
		}
		for(int i=1;;i++){
			for(int j=1;j<=n;j++){
				if(mp[i-a[j]]==1) mp[i]=1;
			}
			if(!mp[i]) ans=max(ans,i);
			nd=clock();
			if((double)nd-strt>=111857){
				if(ans!=-2e9) printf("%lld\n",ans);
				else puts("0");
				break;
			}
		}
	}
	return 0;
}
/*3 2 5 10*/