Description
n支队伍打比赛，每两支队伍恰好比赛一场。平局时各得1分，而有胜负时胜者3分，负者0分。
假设三支队伍得分分别为3, 3, 3，则可能有两种情况：
队伍 A B C 得分
A - 3 0 3
B 0 - 3 3
C 3 0 - 3
队伍 A B C 得分
A - 0 3 3
B 3 - 0 3
C 0 3 - 3
给出n支队伍的最终得分（即所有比赛均已结束），统计有多少种可能的分数表。
Input
第一行包含一个正整数n，队伍的个数。第二行包含n个非负整数，即每支队伍的得分。
Output
输出仅一行，即可能的分数表数目。保证至少存在一个可能的分数表。
Sample Input
样例输入1：
3
3 3 3
样例输入2：
2
0 3
样例输入3：
3
4 1 2
样例输入4：
6
5 6 7 7 8 8
Sample Output
样例输出1：
2
样例输出2：
1
样例输出3：
1
样例输出4：
121
88分方法：
剪枝：
1.如果当前枚举的已经比要求的数大，则退出
2.如果枚举到这里，后面的题全队都小于目标分数，退出
3.如果枚举到倒数第二个，与目标分数的差不为3或0或1，则退出
如果都达到了目标分数，则ans++
如果没到，则枚举三种情况：
①x队赢+3,y队输+0
②x队输+0，y队赢+3
③打平，x队和y队都加1
（Tips：dfs后要回溯）
88分代码如下：
#include<cstdio>
using namespace std;
const int f[]={3,1,0,0};
int n,a[9],ans,p[9];
void dfs(int x,int y)
{
if(p[x]>a[x])return;
if(p[x]+(n-y+1)*3<a[x])return;
if(x==n)
{
ans++;
return;
}
if(y==n)
{
int tmp=a[x]-p[x];
if (tmp==2||tmp>3) return;
p[y]+=f[tmp];
dfs(x+1,x+2);
p[y]-=f[tmp];
}
else
{
p[x]+=3;dfs(x,y+1);p[x]-=3;
p[y]+=3;dfs(x,y+1);p[y]-=3;
p[x]++; p[y]++;dfs(x,y+1);p[x]--;p[y]--;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
dfs(1,2);
printf("%d
",ans);
return 0;
}100分大法来了！！
其实其思想与上诉差不多，主要是加了一个Hash判重，Hash判重是这题最有效的剪枝。
100分代码如下：
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<map>
using namespace std;
const int N=15;
int n,a[N],ans,tmp[N];
map<long long,int>f[N];
int pc(int r,int p,int x);
int dfs(int r)
{
if (r==n)return (!a[n]);
tmp[0]=0;
for (int i=r;i<=n;++i) tmp[++tmp[0]]=a[i];
sort(tmp+1,tmp+tmp[0]+1);
long long h=0;
for (int i=1;i<=tmp[0];++i) h=h*29+tmp[i];
if (f[r].find(h)!=f[r].end()) return f[r][h];
else return f[r][h]=pc(r+1,a[r],r);
}
int pc(int x,int p,int r)
{
if (x>n)
{
if (!p)return dfs(r+1);
else return 0;
}
if ((n-x+1)*3<p)return 0;
int u=0;
if (a[x]>=3)
{
a[x]-=3;
u+=pc(x+1,p,r);
a[x]+=3;
}
if (p>=1&&a[x]>=1)
{
a[x]--;
u+=pc(x+1,p-1,r);
a[x]++;
}
if (p>=3) u+=pc(x+1,p-3,r);
return u;
}
int main (){
scanf ("%d",&n);
for (int i=1;i<=n;++i)scanf("%d",&a[i]);
sort(a+1,a+n+1);
printf("%d",dfs(1));
return 0;
}