题解 P2737 【[USACO4.1]麦香牛块Beef McNuggets】
shadowice1984
2017-10-07 16:41:12
来一发dp
显然，如果我们令dp[i]表示能否凑出i个牛块。
则满足以下递推式
if(dp[i])dp[i+weight[x]]=true;
然后我们需要的就是确定容量。
然后有这样一个结论，
若p，q互质，则任意大于lcf（p，q）-p-q的数都能被p，q表示
然后dp就好~
```cpp
#include<stdio.h>
using namespace std;
int gcd(int a,int b)
{
if(b==0)return a;
else return gcd(b,a%b);
}
int lcf(int a,int b)
{
return a*b/gcd(a,b);
}
bool dp[80000];
int weight[10];
int n;int cont=0x3f3f3f3f;
int res=0;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&weight[i]);
}
int g=weight[0];
for(int i=0;i<n;i++)//确定容量
{
g=gcd(g,weight[i]);
if(g==1)break;
}
if(g!=1)
{
printf("0");return 0;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<=i;j++)
{
int t=lcf(weight[i],weight[j]);
if(cont>t&&gcd(weight[i],weight[j])==1)cont=t;
}
}
dp[0]=true;
for(int i=0;i<n;i++)//dp
{
for(int j=0;j<cont;j++)//每个物品可以多次使用
{
if(dp[j]==true)
{
dp[j+weight[i]]=true;
}
}
}
for(int i=0;i<cont;i++)
{
//printf("dp[%d]is%d\n",i,dp[i]);
if(dp[i]==false)res=i;
}
printf("%d",res);
return 0;//拜拜程序
}
```