题解 P2329 【[SCOI2005]栅栏】

· · 题解

在这里观看更佳

这题的总体思路是：二分答案+贪心+dfs验证 首先，二分答案是不用说的，就看贪心和dfs验证。 如果要使得John得到至少m个木材，那么当然是选择最短的啦。所以可以提前把John需要的木材按规格从小到大排序，这就是贪心。
然后dfs就是如果能提供的木材有比John需要的第x根木材的规格大的（或相等的），那么就试试把这根木材中John需要的部分卖给他。不过……
第一行为整数m(m<= 50)表示木材店老板可以提供多少块木材给约翰。
这么大的数，不超时才怪勒！所以我们需要剪枝。有两个剪枝：

  1. 可行性剪枝，如果剩余的木材都不够John的需要，则return，所以这里需要用到前缀和，还要一个变量存储浪费的木材（即连最短的一根木材都不够）
  2. 去重，如果两根木材的规格相同，则可以去重。

有了这两个剪枝，就可以玄学地过了这题了！
上代码！

#include<bits/stdc++.h>
using namespace std;
int n,m,a[55],b[1100];
int w,l,r,mid,tot,sum[1100];//w是多余的木材，tot是总共能提供的木材的量，sum是John需要的木材的前缀和
bool dfs(int x,int l)
{
    if(tot-w<sum[mid]) return 0;//第一个剪枝
    if(x==0) return 1;//x=0表示还需要0根，也就是可以满足条件了，那么返回true
    bool f=0;
    for(int i=l;i<=n;i++)
     if(a[i]>=b[x])//如果第i根木材可以满足John需要的第x根木材，dfs
     {
        a[i]-=b[x];
        if(a[i]<b[1]) w+=a[i];
        if(b[x-1]==b[x]) f=dfs(x-1,i);//去重
        else f=dfs(x-1,1);
        if(a[i]<b[1]) w-=a[i];
        a[i]+=b[x];
        if(f) return 1;
     }
     return 0;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        tot+=a[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++) cin>>b[i];
    sort(b+1,b+m+1);//排序
    for(int i=1;i<=m;i++) sum[i]=sum[i-1]+b[i];//计算前缀和，注意一定要在排序后计算哦！
    while(sum[m]>tot&&m) m--;//如果选最短的m根都超出了能提供的木材的范围，则一定不可行
    l=0,r=m;
    while(l<=r)//二分
    {
        mid=(l+r)/2;
        if(dfs(mid,1)) l=mid+1;
        else r=mid-1;
    }
    cout<<l-1;
    return 0;
}

谢谢您看到这里，如果觉得这篇题解能帮到您，请您给我一个赞，谢谢！