USACO-Section4.1 Beef McNuggets【动态规划】

本文主要是介绍USACO-Section4.1 Beef McNuggets【动态规划】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

农夫布朗的奶牛们正在进行斗争，因为它们听说麦当劳正在考虑引进一种新产品：麦香牛块。奶牛们正在想尽一切办法让这种可怕的设想泡汤。奶牛们进行斗争的策略之一是“劣质的包装”。“看，”奶牛们说，“如果你只用一次能装3块、6块或者10块的三种包装盒包装麦香牛块，你就不可能满足一次只想买1、2、4、5、7、8、11、14或者17块麦香牛块的顾客了。劣质的包装意味着劣质的产品。”

你的任务是帮助这些奶牛。给出包装盒的种类数N(1<=N<=10)和N个代表不同种类包装盒容纳麦香牛块个数的正整数(1<=i<=256)，输出顾客不能用上述包装盒(每种盒子数量无限)买到麦香牛块的最大块数。如果所有购买方案都能得到满足或者不存在不能买到块数的上限，则输出0。不能买到的最大块数（倘它存在）不超过2,000,000,000。

INPUT FORMAT:

第1行: 包装盒的种类数N

第2行到N+1行: 每个种类包装盒容纳麦香牛块的个数

OUTPUT FORMAT:

输出文件只有一行数字：顾客不能用包装盒买到麦香牛块的最大块数或0(如果所有购买方案都能得到满足或者顾客不能买到的块数没有上限)。

SAMPLE INPUT
3
3
6
10

SAMPLE OUTPUT
17

解题思路：

这道题涉及到数论中的扩展欧几里德定理(用来判断是否无解)，当然正常思维也可以想到，当他们的最大公约数大于1时必然发散。然后在公式ax+by=c中，由于x和y大于1，所以c为x*y-x-y(不知道原因)，但是由于不止两个数，所以c有可能会被取到，所以c可以作为上限来动态规划，取最小的两个互质正整数即可，所以动态规划数组长度的最大值为255*256-255-256，然后设dp[0]=1,判断dp[j-a[i]]是否为true，直到有Min(a数组最小值)个true时return，问题得解。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#define INF 99999999
using namespace std;
FILE *fin,*fout;
int N,a[11];
bool v[66000];
typedef pair<int,int> P;int gcd(int a,int b){return b?gcd(b,a%b):a;
}
int main(){fin  = fopen ("nuggets.in", "r");fout = fopen ("nuggets.out", "w");fscanf(fin,"%d",&N);int temp=0;for(int i=0;i<N;i++){fscanf(fin,"%d",&a[i]);if(temp==0)temp=a[i];temp=gcd(a[i],temp);}if(temp>1)fprintf(fout,"%d\n",0); else{sort(a,a+N);int Min=a[0];memset(v,0,sizeof(v));int temp=1,ccount=0,ans=0;v[0]=true;while(1){for(int i=0;i<N;i++){if(temp<a[i])break;else if(v[temp-a[i]]){v[temp]=true;ccount++;break;}}if(ccount>=Min)break;if(v[temp]==false){ccount=0;ans=temp;}temp++;}fprintf(fout,"%d\n",ans);}exit(0);
}