usaco training 4.1.2 Fence Rails 题解

Farmer John is trying to erect a fence around part of his field. He has decided on the shape of the fence and has even already installed the posts, but he‘s having a problem with the rails. The local lumber store has dropped off boards of varying lengths; Farmer John must create as many of the rails he needs from the supplied boards.

Of course, Farmer John can cut the boards, so a 9 foot board can be cut into a 5 foot rail and a 4 foot rail (or three 3 foot rails, etc.). Farmer John has an `ideal saw‘, so ignore the `kerf‘ (distance lost during sawing); presume that perfect cuts can be made.

The lengths required for the rails might or might not include duplicates (e.g., a three foot rail and also another three foot rail might both be required). There is no need to manufacture more rails (or more of any kind of rail) than called for the list of required rails.

PROGRAM NAME: fence8

INPUT FORMAT

OUTPUT FORMAT

惭愧啊，这道搜索题做得焦头烂额，调了一个多小时，几度想放弃。还好总算成功了！

以前我在VJ上也做到过这道题,但当时一直TLE。

为了叙述方便，我们把原来的木头叫原木，后来切的叫新木。

-------------------------------------------------一开始我的想法-----------------------------------------------------------

首先，把原木和新木快排一遍。

每次二分枚举可以切的木块数，再去验证。

验证时，设枚举的木块数为k。由贪心思想可知，我们挑前k小的新木来切割。

事实证明，每次先用大的原木切割会更快，因为相对来说，它能分的个数更多。（想到以前NOIP2012的文化之旅，倒着搜比正着搜更快）

然后再加点小的剪枝，取新木的前缀和，如果当前试的原木可以切完所有的新木，就直接return真。

可是，到第四个点就TLE了！！！

------------------------------------------------求助互联网--------------------------------------------------------------

太强了！我看到NOCOW里有个题解（新木）：对于切剩下的board（无法再切下rail），统计一下总和。如果这个值大于board长度的总和减去rail长度的总和，一定无解，可以剪枝。这个剪枝最关键。

加了这个剪枝之后，我就立马过了，且最慢的点也才0.11ms。

真心膜拜那位大牛！

代码：（红色为增加代码）

/*
ID:juan1973
LANG:C++
PROG:fence8
*/
 
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[51],b[1024],b_sum[1024],n,m,i,ans,sum,sum2;
bool check(int num,int now,int q,int limit)
{
  if (num==0) return true;
  if (q>limit) return false;
  if (b[num]!=b[num+1]) now=n;
  for (int i=now;i>0;i--)
  {
    if (a[i]>=b_sum[num]) return true;
    if (a[i]>=b[num])
    {
      a[i]-=b[num];
      if (check(num-1,i,q+(a[i]<b[1])?a[i]:0,limit)) {a[i]+=b[num];return true;}
      a[i]+=b[num];
    }
  } 
  return false;
}
int erfen(int l,int r)
{
  if (l==r) return l;
  int mid=(l+r)/2+1;
  if (check(mid,n,0,sum-b_sum[mid])) return erfen(mid,r);
                                     return erfen(l,mid-1);
}
int main()
{
  //freopen("fence8.in","r",stdin);
  //freopen("fence8.out","w",stdout);
  scanf("%ld",&n);
  for (i=1;i<=n;i++) {scanf("%ld",&a[i]);sum+=a[i];}
  sum2=sum;
  sort(a+1,a+n+1);
  scanf("%ld",&m);
  for (i=1;i<=m;i++) scanf("%ld",&b[i]);
  sort(b+1,b+m+1);
  for (i=1;i<=m;i++) b_sum[i]=b_sum[i-1]+b[i];
  for (i=1;i<=m;i++) {sum2-=b[i];if (sum2<0) break;}
  ans=erfen(0,i-1);
  printf("%ld\n",ans);
  //scanf("%ld",&n);
  return 0;
}

usaco training 4.1.2 Fence Rails 题解,布布扣,bubuko.com

usaco training 4.1.2 Fence Rails 题解

原文：http://blog.csdn.net/jiangshibiao/article/details/19929271