bzoj 1306: [CQOI2009]match循环赛【dfs+剪枝】

大力剪枝，最后洛谷上还开了o2才过……

大概这样剪枝：

1.搜索中，一个队当前得分超过要求或者一个队剩下的比赛场数全赢也达不到要求则return；

2.注意到如果平局，最总分的贡献是2，否则是3，所以可以计算出非平局的常数，dfs中记录一下当前非平局有几场，如果超出要求或者剩下的场次全都非平局也达不到要求则return；

3.如果当前队需要全赢剩下的比赛才能达到要求，就直接使他全赢然后跳过与这个对相关的比赛；

4.如果当前队需要全赢剩下的比赛才能达到要求，就直接使他全输然后跳过与这个对相关的比赛，注意，给他对手加分的时候判断一下是否对手超出要求分，是的话就直接退出；

#include<iostream>

#include<cstdio>

using namespace std;

const int N=15,f[]={3,1,0,0};

int n,a[N],b[N],ans,s,m;

inline void dfs(int x,int y,int cw,int w)

{

	if(b[x]>a[x]||b[x]+(n-y+1)*3<a[x]||cw>s||m-w+1+cw<s)

		return;

	if(x==n&&b[x]==a[x])

	{

		ans++;

		return;

	}

    if(b[x]+(n-y+1)*3==a[x])

	{

        b[x]=a[x];

		dfs(x+1,x+2,cw+n-y+1,w+n-y+1);

        b[x]=a[x]-(n-y+1)*3;

        return;

    }

    else if(b[x]==a[x])

	{

		int f=0;

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

		{

			b[i]+=3;

			if(b[i]>a[i])

				f=1;

		}

		if(!f)

			dfs(x+1,x+2,cw+n-y+1,w+n-y+1);

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

			b[i]-=3;

        return;

    }

	else if(y==n)

	{

		int nw=a[x]-b[x];

		if(nw==2)

			return;

		b[y]+=f[nw];

		dfs(x+1,x+2,cw+(nw!=1),w+1);

		b[y]-=f[nw];

	}

	else

	{

		b[x]+=3;

		dfs(x,y+1,cw+1,w+1);

		b[x]-=3;

		b[y]+=3;

		dfs(x,y+1,cw+1,w+1);

		b[y]-=3;

		b[x]++,b[y]++;

		dfs(x,y+1,cw,w+1);

		b[x]--,b[y]--;

	}

}

int main()

{

	scanf("%d",&n);

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

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

	s-=n*(n-1),m=n*(n-1)/2;

	dfs(1,2,0,1);

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

	return 0;

}

巴特西

bzoj 1306: [CQOI2009]match循环赛【dfs+剪枝】

最新文章

热门文章