P2329 [SCOI2005]栅栏

题目描述

农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需要的规格。

而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为10的木板可以切成长度为8和2的两个木板。

你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木材的规格，求约翰最多能够得到多少他所需要的木板。

输入输出格式

输入格式：

第一行为整数\(m(m<= 50)\)表示木材店老板可以提供多少块木材给约翰。紧跟着m行为老板提供的每一块木板的长度。

接下来一行(即第\(m+2\)行)为整数\(n(n <= 1000)\)，表示约翰需要多少木材。

接下来\(n\)行表示他所需要的每一块木板的长度。木材的规格小于\(32767\)。（对于店老板提供的和约翰需要的每块木板，你只能使用一次）。

输出格式：

只有一行，为约翰最多能够得到的符合条件的木板的个数。

比较正常的搜索剪枝题目。

首先我们想对某个东西排个序剪枝一下，因为在搜索中木材的长度是动态的，所以对它排序没得用。

对木板排的话又不能确定上界。

自然的想到二分搞一个上界。

然后我们对木板排序，从大往小放。

剪枝1：当当前木板和下一块等长，下次从同一块木材搜索

剪枝2：找到当前所有还可能贡献答案（剩余长度大于最小的木板）的木材，然后计算是否大于剩下的木板

Code:

#include <cstdio>

#include <algorithm>

int n,m_,m,stick[52],f[1002],need[1002],mi=1<<30;

int dfs(int dep,int s)

{

    if(!dep) return 1;

    int mx=0,sum=0;

    for(int i=1;i<=m;i++)

        if(stick[i]>=need[1])

            sum+=stick[i];

    if(sum<f[dep]) return 0;

    for(int i=s;i<=m;i++)

    {

        if(stick[i]>=need[dep])

        {

            stick[i]-=need[dep];

            mx|=dfs(dep-1,need[dep]==need[dep+1]?i:1);

            stick[i]+=need[dep];

            if(mx) return 1;

        }

    }

    return mx;

}

int main()

{

    scanf("%d",&m_);

    for(int i=1;i<=m_;i++) scanf("%d",stick+i);

    scanf("%d",&n);

    for(int i=1;i<=n;i++) scanf("%d",need+i),mi=mi<need[i]?mi:need[i];

    for(int i=1;i<=m_;i++)

        if(stick[i]>=mi)

            stick[++m]=stick[i];

    std::sort(need+1,need+1+n);

    for(int i=1;i<=n;i++) f[i]=f[i-1]+need[i];

    if(!m) return puts("0"),0;

    int l=1,r=n;

    while(l<r)

    {

        int mid=l+r+1>>1;

        if(dfs(mid,1)) l=mid;

        else r=mid-1;

    }

    printf("%d\n",l);

    return 0;

}

2018.10.10

巴特西

洛谷 P2329 [SCOI2005]栅栏解题报告

P2329 [SCOI2005]栅栏

题目描述

输入输出格式

输入格式：

输出格式：

最新文章

热门文章

巴特西

洛谷 P2329 [SCOI2005]栅栏 解题报告

P2329 [SCOI2005]栅栏

题目描述

输入输出格式

输入格式：

输出格式：

最新文章

热门文章

洛谷 P2329 [SCOI2005]栅栏解题报告