bzoj 1082: [SCOI2005]栅栏【二分+dfs】

二分答案，dfs判断是否可行，当b[k]==b[k-1]时可以剪枝也就是后移枚举位置

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=1005;

int n,a[N],m,b[N],sum,s[N],re,mid,t[N];

bool dfs(int k,int x)

{

    if(k<=0)

		return 1;

    if(s[mid]+re>sum)

		return 0;

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

		if(t[i]>=b[k])

		{

			t[i]-=b[k];

			if(t[i]<b[1])

				re+=t[i];

			if(b[k]==b[k-1])

			{

				if(dfs(k-1,i))

					return 1;

			}

			else if(dfs(k-1,1))

				return 1;

			if(t[i]<b[1])

				re-=t[i];

			t[i]+=b[k];

		}

    return 0;

}

int main()

{

    scanf("%d",&m);

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

		scanf("%d",&a[i]),sum+=a[i];

    scanf("%d",&n);

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

		scanf("%d",&b[i]);

    sort(a+1,a+1+m);

    sort(b+1,b+1+n);

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

		s[i]=s[i-1]+b[i];

    while(b[n]>a[m])

		n--;

    int l=0,r=n,ans=0;

    while(l<=r)

    {

        mid=(l+r)>>1;

        re=0;

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

			t[i]=a[i];

        if(dfs(mid,1))

			l=mid+1,ans=mid;

        else

			r=mid-1;

    }

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

    return 0;

}

巴特西

bzoj 1082: [SCOI2005]栅栏【二分+dfs】

最新文章

热门文章