Fence Rails栅栏的木料

描述﹡﹡﹡﹡﹡

农民John准备建一个栅栏来围住他的牧场。他已经确定了栅栏的形状，但是他在木料方面有些问题。当地的杂货储存商扔给John一些木板，而John必须从这些木板中找出尽可能多所需的木料。

当然，John可以切木板。因此，一个9英尺的木板可以切成一个5英尺和一个4英尺的木料 (当然也能切成3个3英尺的，等等)。John有一把（完美的）梦之锯，因此他在切木料时，不会有木料的损失。

所需要的栅栏长度可能会有重复（比如，一个3英尺和另一个3英尺长的栅栏可能同时都需要）。所需要的木料规格都已经给定。你不必切出更多木料，那没有用。

格式

PROGRAM NAME: fence8

INPUT FORMAT:

(file fence8.in)

第1行: N (1 <= N <= 50), 表示提供的木板的数目

第2行到第N+1行: N行，每行包括一个整数，表示各个木板的长度。

第N+2行: R (1 <= R <= 1023), 所需木料的数目

第N+3行到第N+R+2行: R行，每行包括一个整数(1 <= ri <= 128)表示所需木料的长度。

OUTPUT FORMAT:

(file fence8.out)

只有一行，一个数字，表示能切出的最多的所需木料的数目。当然，并不是任何时候都能切出所有所需木料。

SAMPLE INPUT

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

SAMPLE OUTPUT

7

迭代深化+贪心+二分

/*
 ID:10239512
 PROG:fence8
 LANG:C++    
    */ 
//#include <iostream> 
#include<fstream>
#include<cstring>
using namespace std;
ifstream cin("fence8.in");
ofstream cout("fence8.out");

int n,m,ri[1024],re[1024],ha[51],co[51],total=0,leave,mid;

void Quick(int left,int right,int p){
     if(left>=right) return ;
     if(p==0)
     {
      int mi=ha[(left+right)/2];
      int i=left,j=right;
      while(i<=j)
      {
       while(ha[i]>mi) i++;
       while(ha[j]<mi) j--;
       if(i<=j)
       {swap(ha[i],ha[j]);i++;j--;}
                 }
      Quick(left,j,0);
      Quick(i,right,0);       
             }
      else 
      {
       int mi=ri[(left+right)/2];
       int i=left,j=right;
       while(i<=j)
       {
        while(ri[i]<mi) i++;
        while(ri[j]>mi) j--;
        if(i<=j)
        {swap(ri[i],ri[j]);i++;j--;}
                  }
       Quick(left,j,1);
       Quick(i,right,1);
           }

     }

int Dfsid(int deep,int num){
    if(deep<=0) return 1;
    if(leave+re[mid]>total) return 0;
    for(int i=num;i<=n;++i)
    if(co[i]>=ri[deep])
    {
     co[i]-=ri[deep];
     if(co[i]<ri[1]) leave+=co[i];
     if(ri[deep]==ri[deep-1])
     {if(Dfsid(deep-1,i)) return 1;}
     else if(Dfsid(deep-1,1)) return 1;
     if(co[i]<ri[1]) leave-=co[i];
     co[i]+=ri[deep];
            }
    return 0;
    }


int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    cin>>ha[i],total+=ha[i];

    cin>>m;
    for(int i=1;i<=m;++i)
    cin>>ri[i];

    Quick(1,n,0); 
    Quick(1,m,1);

    for(int i=1;i<=m;++i)
    re[i]=re[i-1]+ri[i];

    while(re[m]>total) m--;

    int left=0,right=m;  mid=m/2;
    while(left<=right)
    {
     for(int i=1;i<=n;++i)
     co[i]=ha[i];
     leave=0;
     if(Dfsid(mid,1))
     {left=mid+1;mid=(left+right)/2;}
     else {right=mid-1;mid=(left+right)/2;}
                      }

    cout<<mid<<endl;
   // system("pause");
    return 0;

    } 



/* 
二分法模板 
erfen()
{
 int l=0,r=m,mid;
 mid=(l+r)/2;
 while(l<=r)
 {
  if()
  {l=mid+1;mid=(l+r)/2;}
  else {r=mid-1;mid=(l+r)/2;} 
            }  
 cout<<mid<<endl; 
       } 

*/

原文链接: https://www.cnblogs.com/noip/archive/2012/07/06/2579908.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍