1 /*
2 ID: hongfei5
3 PROG: fence8
4 LANG: C++
5 */
6 /*
7 dfsid(迭代加深搜索)
8 适用于搜索树又宽又深，但是可行解却不是很深的题目
9 广度优先搜索可能会空间不够
10 */
11 //按大小排序后,则切割的木料中必然包含rail[0]
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 int n,m;//木板和木料的数目
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];//表示已经不能再切的剩下的木料总和
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的价值是相等的——也就是说切小的要比切大的来的划算。那么我们在搜索能否切出i个rail的方案是自然要选最小的i个rail来切
2.经过一些实验可以发现，先切大的rail比先切小的rail更容易提前出解。同样，[先切小的board比先切大的board更容易提前出解？]{注：好像先切大的board要比先切小的更快
3.由于r最大可能是1023，但是rail长度的范围却只有0~128，这点提醒了我们有很多rail的长度会是相同的。所以我们要避免
冗余，优化搜索顺序。若有rail[i+1]=rail[i]，则rail[i+1]对应的board一定大于等于rail[i]对应的board。可以
通过这种方法剪掉很多冗余的枝条
4.相应的，如果board[i]=board[i+1]，那么从board[i]切下的最大的rail一定大于等于从board[i+1]切下的最大的rail
5.对于切剩下的board（无法再切下rail），统计一下总和。如果大于 board长度总和-rail长度总和，一定无解，可以剪枝。