Description

　　農夫約翰打算建立一個柵欄將他的牧場給圍起來，因此他需要一些特定規格的木材。于是農夫約翰到木材店購
買木材。可是木材店老板說他這里只剩下少部分大規格的木板了。不過約翰可以購買這些木板，然后切割成他所需
要的規格。而且約翰有一把神奇的鋸子，用它來鋸木板，不會產生任何損失，也就是說長度為10的木板可以切成長
度為8和2的兩個木板。你的任務：給你約翰所需要的木板的規格，還有木材店老板能夠給出的木材的規格，求約翰
最多能夠得到多少他所需要的木板。

Input

　　第一行為整數m(m<= 50)表示木材店老板可以提供多少塊木材給約翰。緊跟著m行為老板提供的每一塊木板的長
度。接下來一行(即第m+2行)為整數n(n <= 1000)，表示約翰需要多少木材。接下來n行表示他所需要的每一塊木板
的長度。木材的規格小于32767。（對于店老板提供的和約翰需要的每塊木板，你只能使用一次）。

Output

　　只有一行，為約翰最多能夠得到的符合條件的木板的個數。

Sample Input

4
30
40
50
25
10
15
16
17
18
19
20
21
25
24
30

Sample Output

7

HINT

?

25切出 21 30切出 20 40切出 19、18 50切出 15、16、17

題解

二分+dfs判定

我們首先排序一下

這道題我們二分答案，再用dfs判斷一下[1,mid]這段區間是否可行

我們這里是枚舉木板從哪塊木材上切下來（這里用倒著枚舉）

但是普通的dfs判斷是會T的

這里主要講兩個優化：

nlen[i]表示需要的第i塊木板，now表示當前的木板的下標

1.if (nlen[now]==nlen[now-1])的時候我們直接check（now-1,i）為什么是 i 呢，因為前面小的點都被跳過了（nlen[now]都已經要第i塊木材切了，nlen[now-1]和它相等當然至少要從i開始嘍）

2.我們切木材當然是希望木材浪費的越少越好，所以當這塊木材連第一塊木板都切不下（要被浪費了），就把剩下的木材長度加到waste中

如果waste>總木材的和-sum[mid]（如果mid可行的話，最優的切割waste應該是等于的）說明這樣切割不是最優的

1 #include<bits/stdc++.h> 2 #define M 55 3 #define N 1005 4 using namespace std; 5 int n,m,l,r,mid,ans,waste,sum; 6 int len[M],tlen[M]; 7 int nlen[N],s[N]; 8 bool check(int now,int p){ 9 if (!now) return true; 10 if (waste>sum-s[mid]) return false; 11 for (int i=p;i<=m;i++) 12 if (tlen[i]>=nlen[now]){ 13 tlen[i]-=nlen[now]; 14 if (tlen[i]<nlen[1]) waste+=tlen[i]; 15 if (nlen[now]==nlen[now-1]){ 16 if (check(now-1,i)) return true; 17 } else 18 if (check(now-1,1)) return true; 19 if (tlen[i]<nlen[1]) waste-=tlen[i]; 20 tlen[i]+=nlen[now]; 21 } 22 return false; 23 } 24 int main(){ 25 scanf("%d",&m); 26 for (int i=1;i<=m;i++) 27 scanf("%d",&len[i]),sum+=len[i]; 28 scanf("%d",&n); 29 for (int i=1;i<=n;i++) 30 scanf("%d",&nlen[i]); 31 sort(len+1,len+1+m); 32 sort(nlen+1,nlen+1+n); 33 for (int i=1;i<=n;i++) 34 s[i]=s[i-1]+nlen[i]; 35 l=0; r=n; 36 while (l<=r){ 37 mid=(l+r)>>1; 38 waste=0; 39 memcpy(tlen,len,sizeof(len)); 40 if (check(mid,1)){ 41 ans=mid; l=mid+1; 42 } else r=mid-1; 43 } 44 printf("%d\n",ans); 45 return 0; 46 } View Code

?

轉載于:https://www.cnblogs.com/zhuchenrui/p/7622748.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的BZOJ-1082-[SCOI2005]栅栏（二分+dfs判定）的全部內容，希望文章能夠幫你解決所遇到的問題。

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