问题描述
n队伍比赛，每两支队伍比赛一次，平1胜3负0.
给出队伍的最终得分，求多少种可能的分数表。
输入格式
第一行包含一个正整数n，队伍的个数。第二行包含n个非负整数，即每支队伍的得分。
输出格式
输出仅一行，即可能的分数表数目。保证至少存在一个可能的分数表。
样例输入
6
5 6 7 7 8 8
样例输出
121
数据范围
N<=8
解析
这么小的范围肯定是搜索啊。状态即为当前比赛是哪两支队伍在进行，搜索比分表的上三角区域(不包括对角线)。当搜索到第n行时，如果满足要求即可让答案加1。但是我们需要几个剪枝。
- 如果当前某一方加分后超过最终分数，可以剪枝。
- 如果某一方即使后面的比赛全赢也无法到达最终分数，可以剪枝。
- 如果当前是某个人的最后一场比赛，可以直接推出结果。
然后就跑过去了。
代码
#include <iostream>
#include <cstdio>
#define N 10
using namespace std;
int n,i,s[N],a[N],ans;
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
bool check()
{
for(int i=1;i<=n;i++){
if(s[i]!=a[i]) return 0;
}
return 1;
}
void dfs(int x,int y)
{
if(x==n){
if(check()) ans++;
return;
}
if(a[x]+3*(n-y+1)<s[x]) return;
if(y==n){
if(s[x]-a[x]==1){
a[x]++;a[y]++;
dfs(x+1,x+2);
a[x]--;a[y]--;
}
else if(s[x]-a[x]==0||s[x]-a[x]==3){
int tmpx=a[x],tmpy=a[y];
a[y]+=3-(s[x]-a[x]);
a[x]=s[x];
dfs(x+1,x+2);
a[x]=tmpx,a[y]=tmpy;
}
return;
}
if(a[x]+1<=s[x]&&a[y]+1<=s[y]){
a[x]++;a[y]++;
dfs(x,y+1);
a[x]--;a[y]--;
}
if(a[x]+3<=s[x]){
a[x]+=3;
dfs(x,y+1);
a[x]-=3;
}
if(a[y]+3<=s[y]){
a[y]+=3;
dfs(x,y+1);
a[y]-=3;
}
}
int main()
{
n=read();
for(i=1;i<=n;i++) s[i]=read();
dfs(1,2);
cout<<ans<<endl;
return 0;
}