小凯的疑惑升级版。只有两个数的话不能表示的最大数是ab-a-b,显然如果可选数增加不会比这更大,所以只要答案存在一定小于256*256-2*256。在这个范围内背包即可。
#include#include #include #include #include #include using namespace std;int read(){ int 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^48),c=getchar(); return x*f;}#define N 12int n,a[N];bool f[70000];int main(){#ifndef ONLINE_JUDGE freopen("cow.in","r",stdin); freopen("cow.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(); for (int i=1;i<=n;i++) a[i]=read(); f[0]=1; for (int j=1;j<70000;j++) for (int i=1;i<=n;i++) if (j>=a[i]) f[j]|=f[j-a[i]]; if (!f[69999]) {cout<<0;return 0;} for (int i=69999;i>=0;i--) if (!f[i]) {cout<