----

----

2
4
5

6

2
4
6

INF

CPU消耗  < 1000ms

main函数需要返回0;

—————————————————————————————————————————————

dp[i][j]表示前i个数是否能组合成j,如果能的话dp[i][j]值为1，如果不能的话dp[i][j]为0；

``````#include<stdio.h>
const int INF = 10000;
int dp[INF + 1]={0};
int Complete Pack(int a, int b);//二进制优化的完全背包

int CompletePack1(int a);//优化后的完全背包 ，在这里我们用这个背包

int ZeroOnePack(int a, int b); //用于二进制优化的完全背包

int gcd(int a, int b);
int main()
{
int num[INF + 1], n;

scanf("%d",&n);

for(int i = 1; i <= n; i++)
scanf("%d",&num[i]);

bool is = false;

for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(i != j)
{
if(gcd(num[i], num[j]) == 1)
is = true;
break;
}
}
}

if(!is)
printf("INF\n");
else
{
dp[0] = 1;
/*
for(int i=1;i<=n;i++)
{
CompletePack(num[i],INF);在这里我们用下面那个完全背包
}
*/
for(int i = 1;i <= n; i++)
{
CompletePack1(num[i]);
}

int result = 0;

for(int i = 1; i <= INF; i++)
{
if(dp[i] == 0)
printf("%d ",i), result++;
}
printf("\n%d\n",result);
}

return 0;
}
int CompletePack1(int a)
{
for(int i = a; i <= INF; i++)
{
if(dp[i - a] == 1)
dp[i] = 1;
}
return 0;
}
int CompletePack(int a, int b)
{
int ans = 1;
while(ans < b)
{
ZeroOnePack(a * ans, INF);
b -= ans;
ans <<= 1;
}
ZeroOnePack(a * b, INF);
return 0;
}
int gcd(int a ,int b)
{
if(b > a)
return gcd(b, a);

return b == 0 ? a : gcd(b, a % b);

}
int ZeroOnePack(int a, int b)
{
for(int j = b; j >= a; j--)
{
if(dp[j - a] == 1)
dp[j] = 1;
}
return 0;
}``````