【BZOJ】【P 1306】【CQOI 2009】【マッチサイクル】【問題解】【検索+枝切り】

転送ゲート:
http://www.lydsy.com/JudgeOnline/problem.php?id=1306
この問題はひどく私に一言教えてくれた:切ることができるなら切らなければならない!!!
枝を切るのはとても簡単ですが、全部加えなければなりません.
①nチームは(n*(n-1)/2試合を行い、一つのチームが勝つか別のチームが負けるかを列挙する
②各チームが最後の試合まで列挙したときに直接計算できる
③現在の得点が目標点数より大きい場合はreturn
④今後全勝しても目標点数に届かなければreturn
しまった、全部プラスして7 s過ぎ、こんにゃくはrank 1 15 msがどのように過ごしたのか想像しにくい......
Code:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int sor[9];
int nowsor[9];
int mp[9][9];
int ans=0;
bool ok(){
	for(int i=1;i<=n;i++)
	if(sor[i]!=nowsor[i])
	return false;
	return true;
}
inline void dfs(int a,int b){	      
	if(a>=n){
		if(sor[n]==nowsor[n])
		ans++;
		return;
	}
	int i=b+1;
	if(i==n){
		int k=sor[a]-nowsor[a];
		if(k==0){
			nowsor[a]+=0;nowsor[i]+=3;
			mp[a][i]=0;mp[i][a]=3;
			if(nowsor[a]<=sor[a]&&nowsor[i]<=sor[i]
				&&nowsor[a]+3*(n-i)>=sor[a]
				&&nowsor[i]+3*(n-a)>=sor[i])
			dfs(a+1,a+1);
			nowsor[a]-=0;nowsor[i]-=3;			
		}else
		if(k==1){
			nowsor[a]+=1;nowsor[i]+=1;
			mp[a][i]=1;mp[i][a]=1;
			if(nowsor[a]<=sor[a]&&nowsor[i]<=sor[i]
				&&nowsor[a]+3*(n-i)>=sor[a]
				&&nowsor[i]+3*(n-a)>=sor[i])
			dfs(a+1,a+1);
			nowsor[a]-=1;nowsor[i]-=1;				
		}else
		if(k==3){
			nowsor[a]+=3; nowsor[i]+=0;
			mp[a][i]=3;   mp[i][a]=0;
			if(nowsor[a]<=sor[a]&&nowsor[i]<=sor[i]
				&&nowsor[a]+3*(n-i)>=sor[a]
				&&nowsor[i]+3*(n-a)>=sor[i])
			dfs(a+1,a+1);
			nowsor[a]-=3; nowsor[i]-=0;			
		}
	
	}else{
		nowsor[a]+=3; nowsor[i]+=0;
		mp[a][i]=3;   mp[i][a]=0;
		if(nowsor[a]<=sor[a]&&nowsor[i]<=sor[i]
			&&nowsor[a]+3*(n-i)>=sor[a]
			&&nowsor[i]+3*(n-a)>=sor[i])
		dfs(a,b+1);
		nowsor[a]-=3; nowsor[i]-=0;	
				
		nowsor[a]+=1;nowsor[i]+=1;
		mp[a][i]=1;mp[i][a]=1;
		if(nowsor[a]<=sor[a]&&nowsor[i]<=sor[i]
			&&nowsor[a]+3*(n-i)>=sor[a]
			&&nowsor[i]+3*(n-a)>=sor[i])
		dfs(a,b+1);
		nowsor[a]-=1;nowsor[i]-=1;	
					

		nowsor[a]+=0;nowsor[i]+=3;
		mp[a][i]=0;mp[i][a]=3;
		if(nowsor[a]<=sor[a]&&nowsor[i]<=sor[i]
			&&nowsor[a]+3*(n-i)>=sor[a]
			&&nowsor[i]+3*(n-a)>=sor[i])
		dfs(a,b+1);
		nowsor[a]-=0;nowsor[i]-=3;
	}
	
	
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&sor[i]);
	dfs(1,1);
	cout<<ans<<endl;
	return 0;
}