題目鏈接：點擊查看

題目大意：給定M個不同的得分方式，以及需要得到N分，至少需要多少次（多余N都不行，只能嚴格等于N）

思路：第一反應肯定是完全背包，可是N給到了1e9的程度，開數組肯定是開不了的，這個時候就要思考該怎樣優化。

優化方法：鴿巢原理（抽屜原理）：

復制一段學長PPT課件上的證明：

?在鴿巢原理的介紹里面，有例題介紹：設a1,a2,a3,……am是正整數的序列，試證明至少存在正數k和l，1<=k<=l<=m,是的和ak+ak+1+……+al是m的倍數，接下來開始證明：

?構造一個序列s1=a1,s2=a1+a2，……，sm=a1+a2+……+am,那么會產生兩種可能：

?1：若有一個sn是m的倍數，那么定理成立：

?2：假設上述的序列中沒有任何一個元素是m的倍數，令rh ≡ sh mod m;其中h=1,2,……,m;我們已知上面的所有項都非m的倍數，得到s1模m的余數是r1,s2模m的余數是r2,同理往下類推，r是一個余數序列，在這里所有的余數都不為0，因為假設是不存在有m的倍數的，所以r序列的元素小于m，根據抽屜原理（鴿巢原理），m個余數在[1,m-1]區間里的取值至少存在一對rh,rk，并且滿足 rh=rk,即sh和sk滿足

?sk ≡ sh mod m，那么假設h>k，得到?

?sh-sk = (a1+a2+……+ah) - (a1+a2+……+ak)

?sh - sk =ak+1 +ak+2 +……+ah ≡ 0 mod m（此處的k是序列a的下標）

?證明到此結束；

因為這個題目中的M最大只有100，而得分最大maxscore為100，故可以將n的復雜度降至100*100=1e4，這樣就可以用完全背包解決了。上代碼：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e4+200;int dp[N];int w[N];int main() { // freopen("input.txt","r",stdin);int t;cin>>t;while(t--){int n,m;scanf("%d%d",&m,&n);for(int i=1;i<=m;i++)scanf("%d",w+i);sort(w+1,w+1+m);int num=0;if(n>10000){ /* num=(n-(n%w[m])-10000)/w[m];n=n%w[m]+10000;*/int temp=(n-10000)%w[m]+10000;num=(n-temp)/w[m];n=temp;}memset(dp,inf,sizeof(dp));dp[0]=0;for(int i=1;i<=m;i++)for(int j=w[i];j<=n;j++)dp[j]=min(dp[j],dp[j-w[i]]+1);if(dp[n]==inf)cout<<-1<<endl;elsecout<<dp[n]+num<<endl;}return 0; }

注意：注釋掉的那兩行是之前一直不理解的，因此一直沒寫對。

正確利用鴿巢原理降低復雜度，即：

當n大于動態規劃最大處理范圍時（1e4），超過的部分即可以直接用w[m]（最大的得分）來補全，未超過的部分可以交給動態規劃來解決，剩下的問題就是如何將n劃分為超過的部分和需要處理的部分了。

先假設n大于1e4，再假設num為n超過1e4部分所需要w[m]的個數，容易知道，num=（（n-10000）-多余的部分）/w[m]。

因為（n-10000）不一定能整除w[m]，故我們希望能夠將多余的部分交給動態規劃來解決，那么就可以得到多余的部分就是

（n-10000）%w[m]，所以num=（（n-10000）-（n-10000）%w[m]）/w[m]，而原本動態規劃只需要處理1e4，現在多出來了多余的部分，所以n可以降低成n=（n-10000）%w[m]+10000，化簡一下即為上述代碼中的處理部分。

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的ZOJ - 2955 Interesting Dart Game(鸽巢原理+完全背包)的全部內容，希望文章能夠幫你解決所遇到的問題。

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