解题思路:
注意事项:
参考代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#define MAXN 10010 //最多凑出的包子个数为100*100
using namespace std;
int n;
bool dp[MAXN]; //没有初始化默认为假
int a[105];
int pd(int a,int b)
{
if(b==0) return a;
else pd(b,a%b);
}
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
int yueshu=a[1];
for(int i=2; i<=n; i++)
yueshu=pd(yueshu,a[i]);
if(yueshu!=1)
{
printf("INF\n");
}
else
{
dp[0]=true;
for(int i=1; i<=n; i++)
for(int j=0; j+a[i]<=MAXN; j++)
{
if(dp[j])
{
dp[j+a[i]]=true;
}
}
int count=0;
for(int i=0; i<=MAXN; i++)
if(dp[i]==false) count++;
printf("%d\n",count);
}
return 0;
}
/*思路:
完全背包问题
扩展欧几里德变形定理:如果有的包子种类的最大公约数不是1 那么凑不出来的情况就有无限多种
剩下的用完全背包解决
dp[i]数组里存放着是数量为i个的包子数能不能被凑出来*/
0.0分
1 人评分
【回文数(二)】 (C++代码)浏览:874 |
简单的a+b (C语言代码)浏览:676 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:518 |
剪刀石头布 (C语言代码)浏览:754 |
C语言程序设计教程(第三版)课后习题9.1 (C语言代码)浏览:682 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:690 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:669 |
DNA (C语言代码)浏览:741 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:520 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:559 |