這兩天賊煩，ccf炸了，還有一個煩心事。哎我都不知道自己能不能堅持下去了。馬上期末考了。這段時間還是抓緊時間復習吧同時刷usaco的節奏要跟以前一樣了，畢竟課少了。

題解：

只要你知道以下的數論結論，這道題就是水背包了：

有兩個數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）。

而且數越多，這個值只會越小。

所以我們只需考慮小于pq-q-p的范圍的最小值。對于一些無解的（全體最大公約數>1)，或無數解的（有一個‘1’），應提前判斷。 其實我們可以干脆全取上界為256*256-256*2

分析：第一步：判斷這 n 個數的gcd，如果  gcd!= 1 則無解；
     第二步：如果 gcd=1 則解小于最大的兩個數的LCM。
     第三步：背包，使用標記數組 d[]，d[i]=d[i-a[j]];
簡單證明一下：
第一步：
     a1*x1+a2*x2+……+an*xn = p;
     a1*y1+a2*y2+……+an*yn = p+1;
所以：a1*(y1-x1)+a2*(y2-x2)+……+an*(yn-xn) = 1;
所以：gcd(a1,a2,……,an)*[a1/gcd(a1,a2,……,an)*(y1-x1) + a2/gcd(a1,a2,……,an)*(y2-x2) +……+ an/gcd(a1,a2,……,an)*(yn-xn)]=1（a）
所以：gcd(a1,a2,……,an)=1;
第二步：……

以上證明就是證明紅字部分要讓大于這個數所有的數都可以表示明顯p可以，則p+1肯定可以。得到a式。用反證法證明一下即可知gcd(a1-an)=1;

[a1/gcd(a1,a2,……,an)*(y1-x1) + a2/gcd(a1,a2,……,an)*(y2-x2) +……+ an/gcd(a1,a2,……,an)*(yn-xn)]=1/gcd(a1,a2,……,an);

因為等式左邊是整數等式右邊也是整數所以只能等于1；

然后就是dp找到所有狀態。從大到小看那個狀態不存在。

/*
ID:jinbo wu
LANG:C++
TASK: nuggets
*/ 
#include<bits/stdc++.h>
using namespace std;
int dp[256*256];
int a[15];
int gcd(int b,int c)
{if(c==0)return b;return gcd(c,b%c);
}
bool cmp(int a,int b)
{return a>b;
}
int main()
{freopen("nuggets.in","r",stdin);freopen("nuggets.out","w",stdout);int n;cin>>n;for(int i=0;i<n;i++)cin>>a[i];int g=a[0];if(n==1){cout<<"0"<<endl;return 0;}for(int i=1;i<n;i++){g=gcd(g,a[i]);if(g==1)break;}if(g!=1){cout<<"0"<<endl;return 0;}sort(a,a+n,cmp);dp[0]=1;int sum=a[0]*a[1]-a[0]-a[1];for(int i=0;i<n;i++){for(int j=a[i];j<=sum;j++){if(dp[j-a[i]])dp[j]=1;}}for(int i=sum;i>=0;i--){if(!dp[i]){cout<<i<<endl;return 0;}} 
}

總結

以上是生活随笔為你收集整理的usaco Beef McNuggets的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。