1 /*
2 ID: hongfei5
3 PROG: fence8
4 LANG: C++
5 */
6 /*
7 dfsid(迭代加深搜索)
8 適用于搜索樹(shù)又寬又深，但是可行解卻不是很深的題目
9 廣度優(yōu)先搜索可能會(huì)空間不夠
10 */
11 //按大小排序后,則切割的木料中必然包含rail[0]
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 int n,m;//木板和木料的數(shù)目
16 int rail[1025];
17 int board[51];
18 int remain[51];
19 int best;
20 long sum;
21 long long waste,maywaste,tot[1025];//表示已經(jīng)不能再切的剩下的木料總和
22 void dfs(int dep,int digit)
23 {
24 if(dep==0)
25 {
26 for(int i=digit;i<n;++i)
27 if(remain[i]>=rail[0])
28 {
29 printf("%d\n",best);
30 exit(0);
31 }
32 return ;
33 }
34 for(int i=digit;i<n;++i)
35 if(remain[i]>=rail[dep])
36 {
37 long long oldwaste=waste;
38 remain[i]-=rail[dep];
39 if(remain[i]<rail[0]&&waste+remain[i]>maywaste)
40 {
41 remain[i]+=rail[dep];
42 continue;
43 }
44 if(remain[i]<rail[0])waste+=remain[i];
45 if(rail[dep-1]==rail[dep])dfs(dep-1,i);//如果rail[i]==rail[i-1],而第i塊木料在第K塊木板上切的，那么第i-1塊木料必定在大于等于K的木板上切出
46 else dfs(dep-1,0);
47 remain[i]+=rail[dep];
48 waste=oldwaste;
49 }
50 }
51 int main()
52 {
53 freopen("fence8.in","r",stdin);
54 freopen("fence8.out","w",stdout);
55 scanf("%d",&n);
56 for(int i=0;i<n;++i)
57 {
58 scanf("%d",&board[i]);
59 remain[i]=board[i];
60 sum+=board[i];
61 }
62 scanf("%d",&m);
63 for(int i=0;i<m;++i)
64 scanf("%d",&rail[i]);
65 sort(board,board+n);
66 sort(rail,rail+m);
67 tot[0]=rail[0];
68 int k=0;
69 while(k<m && tot[k]<=sum){ //剪枝方法1
70 ++k;
71 tot[k]=tot[k-1]+rail[k];
72 }
73 m=k;
74 for(int i=m-1;i>=0;--i)
75 {
76 waste=0;
77 maywaste=sum-tot[i];
78 best=i+1;
79 dfs(i,0);
80 }
81 printf("0\n");
82 return 0;
83 }
迭代加深搜索 并不一定都要加深搜索深度 此題就是逐漸減少深
1.很容易就能注意到，由于每塊rail的價(jià)值是相等的——也就是說(shuō)切小的要比切大的來(lái)的劃算。那么我們?cè)谒阉髂芊袂谐鰅個(gè)rail的方案是自然要選最小的i個(gè)rail來(lái)切
2.經(jīng)過(guò)一些實(shí)驗(yàn)可以發(fā)現(xiàn)，先切大的rail比先切小的rail更容易提前出解。同樣，[先切小的board比先切大的board更容易提前出解？]{注：好像先切大的board要比先切小的更快
3.由于r最大可能是1023，但是rail長(zhǎng)度的范圍卻只有0~128，這點(diǎn)提醒了我們有很多rail的長(zhǎng)度會(huì)是相同的。所以我們要避免
冗余，優(yōu)化搜索順序。若有rail[i+1]=rail[i]，則rail[i+1]對(duì)應(yīng)的board一定大于等于rail[i]對(duì)應(yīng)的board。可以
通過(guò)這種方法剪掉很多冗余的枝條
4.相應(yīng)的，如果board[i]=board[i+1]，那么從board[i]切下的最大的rail一定大于等于從board[i+1]切下的最大的rail
5.對(duì)于切剩下的board（無(wú)法再切下rail），統(tǒng)計(jì)一下總和。如果大于 board長(zhǎng)度總和-rail長(zhǎng)度總和，一定無(wú)解，可以剪枝。