USACO Section 4.1 Fence Rails - 用DFSID解多维背包..

这题自己想了两天~~~各种超时...还是只能去拜读好些多大牛的文章..才搞定这题..这题真的很好很典型很经典阿..用到的主体思想是DFSID..为辅的是二分答案~~

所谓DFSID既是迭代加深搜索...名字挺玄乎~~实质上就是先确定一个搜索的层数..然后用DFS搜完整棵树..如果没找到解..那么层数再放深一些..再次DFS搜整棵树..直道搜出解为止..很类似BFS了..但是是用DFS来实现的..空间节约了N多..时间上也没有慢多少..

而这道题..就是枚举答案..也就是输出的那个能切出来的rail最大个数...稍微想下,若最大个数为K..那么肯定是前K小的rail...这样更加方便来枚举答案..若K这个解切不出..那么看K/2..若切得出至少一种方案看K*2..然后不断夹逼得出答案...也就是二分的枚举答案..确定一个数后..就以不超过这个数层数来DFS找有没有至少一个解~~

光是这样还不够..DFS时要剪枝~~NOCOW给的剪枝确实非常之强劲阿...

1. 很容易就能注意到，由于每块rail的价值是相等的——也就是说切小的要比切大的来的划算。那么我们在搜索能否切出i个rail的方案是自然要选最小的i个rail来切。 ----这似乎是我唯一自己能想到的..
2. 经过一些实验可以发现，先切大的rail比先切小的rail更容易提前出解。同样，[先切小的board比先切大的board更容易提前出解？]{注：好像先切大的board要比先切小的更快}。{*我的程序先切小再切大第5个点就TLE了,而先切大再切小就快很多,见C++程序.{跟我一样，握个手，一定要先大后小！！！}} ----这个感觉说不出个所以然..有谁能证明下吗？我的程序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长度的总和，一定无解，可以剪枝。这个剪枝最关键。 ---- 最最牛屎彪悍的剪枝~~这个真的是很巧妙...但仔细想也应该能够想到..这里似乎没说得太明白..我是看了其他人的博客..所谓剩下的board就是将所有剩余木板长度小于最小rail长度的这些剩余长度加起来..board长度总合就是1~N个木板长度的总合..rail长度总和是当前DFSID时确定个数K的前K小的rail长度总和..
6. 二分答案 -- 必须的..一个一个的枚举过去铁超时..
7. 其实在读入的过程中，如果rail[i] > max{board} 那么这个rail应该舍去 By Clarkok

Orz了..总之这道题是学习了！！！！

Program:

/*  
ID: zzyzzy12   
LANG: C++   
TASK: fence8
*/      
#include<iostream>      
#include<istream>  
#include<stdio.h>      
#include<string.h>      
#include<math.h>      
#include<stack>
#include<map>
#include<algorithm>      
#include<queue>   
#define oo 2000000000  
#define ll long long  
#define pi (atan(2)+atan(0.5))*2 
using namespace std;
int s[55],a[1030],N,R,have[55],mystack[1030],sums;
bool ok(int R)
{
      int i,k=1,dep=0,sum=sums,m=0;
      for (i=1;i<=N;i++) have[i]=s[i]; 
      for (i=1;i<=R;i++) sum-=a[i];
      while (1)
      {
            for (i=k;i<=N;i++)
               if (have[i]>=a[R-dep]) break;
            if (i==N+1) 
            {     
                   if (!dep) return false;  
                   k=mystack[dep];                  
                   dep--; 
                   if (have[k]<a[1]) m-=have[k];
                   have[k]+=a[R-dep];
                   k++;
            }else
            {  
                   have[i]-=a[R-dep];  
                   if (have[i]<a[1]) m+=have[i];
                   mystack[++dep]=i;
                   if (dep==R) return true; 
                   if (m>sum) 
                   { 
                         dep--;
                         if (have[i]<a[1]) m-=have[i];
                         have[i]+=a[R-dep]; 
                         k=i+1;  
                         continue;
                   }
                   if (a[R-dep]==a[R-dep-1]) k=i; 
                      else k=1;    
            }           
      }
      return false;   
}
void getanswer(int R)
{
      int l,r=1,mid,w,i;       
      while (r<=R && ok(r)) r*=2;             
      l=r/2;  
      if (r>R) r=R+1;
      while (r-l>1)
      {
            mid=(l+r)/2;    
            if (ok(mid)) l=mid;  
               else r=mid;  
      }   
      printf("%d\n",l); 
      return;
}  
bool cmp(int a,int b)
{
      return a>b;    
}
int main()  
{  
      freopen("fence8.in","r",stdin);   
      freopen("fence8.out","w",stdout);    
      int i;
      sums=0; 
      scanf("%d",&N);
      for (i=1;i<=N;i++) 
      {
            scanf("%d",&s[i]); 
            sums+=s[i];
      }  
      sort(s+1,s+1+N,cmp);
      scanf("%d",&R);
      for (i=1;i<=R;i++) 
         scanf("%d",&a[i]); 
      sort(a+1,a+1+R);
      while (R>=0 && a[R]>s[1]) R--; 
      while (N>=0 && s[N]<a[1]) N--;  
      mystack[0]=0; a[0]=0;
      getanswer(R); 
      return 0;     
}