本文主要是介绍1251 - zlly长了一张包子脸，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1251 - zlly长了一张包子脸
- Time Limit: 1000 ms
- Memory Limit: 65535 Kb
Description
zlly长了一张包子脸，他特别喜欢吃糖果，现在他手头有若干种糖果，每种糖果有个口味值，每种糖果有无数多个。然后娄童鞋也非常喜欢吃糖果，他的口味特别广泛，他喜欢各种各样的口味值，他要求zlly用现有的口味值拼出新的口味值。现在，娄童鞋想知道他不能吃到的口味值最大是多少？你能帮他的忙吗？
举个例子，现在zlly手头有3,6,10三种糖果，他拼不出口味值为1、2、4、5、7…17的糖果，所以结果就是17。
另外，糖果种类数<=10，每种糖果的口味值<=265，可以保证最大的结果不超过2,000,000,000。如果都可以拼出或最大值不存在，输出0。
举个例子，现在zlly手头有3,6,10三种糖果，他拼不出口味值为1、2、4、5、7…17的糖果，所以结果就是17。
另外，糖果种类数<=10，每种糖果的口味值<=265，可以保证最大的结果不超过2,000,000,000。如果都可以拼出或最大值不存在，输出0。
Input
Line 1：糖果的数目n
Line 2..n+1:各种糖果的口味值;
输入文件有多case
Line 2..n+1:各种糖果的口味值;
输入文件有多case
Output
最大拼不出的口味数
Sample Input
3 3 6 10
Sample Output
17
Author
Source
The First ACM-ICPC Nanjing Invitational Tournament
有两个数p,q,且gcd(q,p)=1,则最大无法表示成px+qy（x>=0,y>=0)的数是pq-q-p（对于n>pq-q-p,都可以表示成px+qy；而pq-q-p,就无法表示成px+qy）。
PS:http://www.nocow.cn/index.php/USACO/nuggets
#include <cstring>
#include <memory>
#include <algorithm>
#include <cstdio>
using namespace std;
#define MAX 265*265
bool dp[MAX+1];
int num[11];
int gcd ( int a, int b )
{
if ( a < b ) swap(a,b);
int temp = b;
if ( a % b )
{
temp = a;
a = b;
b = temp % b;
}
return b;
}
int main()
{
int n, i, j, k;
while ( scanf("%d",&n) != -1 )
{
for ( i = 1; i <= n; i++ )
scanf("%d",&num[i]);
k = num[1];
for ( i = 2; i <= n; i++ )
k = gcd ( k, num[i] );
if ( k != 1 )
{
printf("0\n");
continue;
}
memset(dp,0,sizeof(dp));
dp[0] = true;
for ( i = 1; i <= MAX; i++ )
{
for ( j = 1; j <= n; j++ )
if ( i >= num[j] )
dp[i] = dp[i] || dp[i-num[j]];
}
int res = 0;
for ( i = MAX; i >= 1; i-- )
if ( ! dp[i] )
{
res = i;
break;
}
printf("%d\n",res);
}
return 0;
}
这篇关于1251 - zlly长了一张包子脸的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
