Fence Rails USACO 4.1（继续阵亡，DFSID+二分搜索+剩余记录）

额，开始感觉有点像多重背包的问题，但是背包太多了，要是几个背包估计还能用多维背包过去。

后来想着朴素dfs，然后果然如题解所说，只能过3个，后面就太慢了。

NOCOW说用DFSID,这个表示没听说过，于是找了下相关记录

http://enc.tfode.com/DFSID这是一个解释，字面意思就是深度迭代的dfs，不过又说是bfs+dfs，有点搞不清楚了...

看了看NOCOW上大牛的题解，大概明白了点，好像就是在dfs里添加一个深度限制，能到达这个限制就判断这次dfs成功。

可是光这样还是过不去，后面又看到提出二分搜索的优化，由于肯定开始要把rails和broads排序，而且坑定先从小的几个rails开始

判断，二分确实可以提高。但是还是剪枝不够。

于是又有几点剪枝

1.用个wd[i]记录从rail[0]到rail[i]总共长度,total记录broad的总长度，若wd[m]>total，则rail的总数m--，后面的rail肯定剪不出来。这是在搜索前的优化

2.用了全局的 int space 变量，每次dfsid前=0，该变量的作用是，每次发现rail可以从当前broad切出来时，broad自己减少后，

判断该broad是否小于rail[0]，若小于，一定不能用，就该舍弃。space+=该broad，记录舍弃的材料。

每次dfs前判断space>total-wd[mid-1]，mid是深度要求，若为真，表示减去的过多，后面的无需判断，return false；

不过要记得return后 space 要-=broad，切记

3.推荐采用从最大rail开始向前找，且若rail[m]==rail[m-1],表示两个一样长，那么若rail[m]在broad[i]处可切，

那么再次dfs时，搜索的起点一定是i，此时dfsid（m-1，i），不一样就dfsi的（m-1，1）从头搜吧。

  1 /*
  2 
  3 ID: hubiao cave
  4 
  5 PROG: fence8
  6 
  7 LANG: C++
  8 
  9 */
 10 
 11 
 12 
 13 
 14 #include<iostream>
 15 
 16 #include<fstream>
 17 
 18 #include<algorithm>
 19 
 20 using namespace std;
 21 
 22 
 23 
 24 bool dfsid(int,int );
 25 int remain[51],rnum;
 26 int wood[2000],wnum;
 27 
 28 int wd[2000];
 29 int space,mid,total;
 30 bool used[2000];
 31 
 32 int main()
 33 
 34 {
 35 
 36 
 37     ifstream fin("fence8.in");
 38     ofstream fout("fence8.out");
 39 
 40 
 41     fin>>rnum;
 42     for(int i=0;i<rnum;i++)
 43     {
 44         fin>>remain[i];
 45         total+=remain[i];
 46     }
 47     fin>>wnum;
 48     for(int i=0;i<wnum;i++)
 49         fin>>wood[i];
 50 
 51     sort(remain,remain+rnum);
 52     sort(wood,wood+wnum);
 53 
 54     for(int i=0;i<wnum;i++)
 55     {
 56         if(i==0)
 57             wd[i]=wood[i];
 58         else
 59             wd[i]=wood[i]+wd[i-1];
 60     }
 61 
 62     while(wd[wnum-1]>total)
 63         wnum--;
 64     //dfs(0);
 65 
 66     int left=1,right=wnum;
 67     int cnt=0;
 68     while(left<=right)
 69     {
 70         mid=(left+right)/2;
 71         space=0;
 72         if(dfsid(mid-1,0))
 73         {
 74             cnt=max(cnt,mid);
 75             left=mid+1;
 76         }
 77         else
 78         {
 79             right=mid-1;
 80         }
 81     }
 82 
 83 
 84     fout<<cnt<<endl;
 85 
 86 
 87     
 88 
 89     return 0;
 90 
 91 
 92 }
 93 bool dfsid(int m,int start)
 94 {
 95     if(m<0)
 96         return true;
 97     if(space>total-wd[mid-1])
 98         return false;
 99     for(int i=start;i<rnum;i++)
100     {
101         if(!used[m]&&remain[i]>=wood[m])
102         {
103             used[m]=1;
104             remain[i]-=wood[m];
105             if(remain[i]<wood[0])
106                 space+=remain[i];
107             if(wood[m]==wood[m-1])
108             {
109                 if(dfsid(m-1,i))
110                 {
111                 remain[i]+=wood[m];
112                 used[m]=0;
113                     return true;
114                 }
115             }
116             
117             else if(dfsid(m-1,0))
118             {            
119                 remain[i]+=wood[m];
120                 used[m]=0;
121                 return true;
122             }
123             if(remain[i]<wood[0])
124                 space-=remain[i];
125             remain[i]+=wood[m];
126             used[m]=0;
127         }
128     }
129     return false;
130 
131 
132 }