预先警告：我的做法代码量比较大
看完题目后看到数据n<=8,
不难想到这题可以写深搜来做
分析
比如说以数据：
3 3 3 3为例子，
进行了三场比赛：AB AC BC；
我们只要搜索每场比赛，并枚举比赛的三个结果（胜、负、平）并判断能否达到答案的分数即可
如果是三个人：
void dfs(int step) {
if(step==cs+1){
int ff=1;
for(int i=1;i<=n;i++)
if(a[i]!=s[i]) ff=0;
if(ff)
ans++;
return;
}
int x=team3[step][0],y=team3[step][1];//team数组记录了每场比赛的两个参与者
if(s[x]+3<=a[x]){//结局1 A胜
s[x]+=3;
dfs3(step+1);
s[x]-=3;//回溯
}
if(s[y]+3<=a[y]){////结局2 B胜
s[y]+=3;
dfs3(step+1);
s[y]-=3;
}
if(s[x]+1<=a[x]&&s[y]+1<=a[y]){//结局3 平
s[x]++;
s[y]++;
dfs3(step+1);
s[y]--;
s[x]--;
}
}
这样搜索的初步就算完成了
然而分析一下时间复杂度
由于我们搜索的是每一局比赛，每个比赛有三种结果，最多可能有（8*7/2）28场比赛，那么当n8时，时间复杂度为O(3^28(≈2.2e13)) 若不加剪枝肯定会T；
所以要加上一些剪枝
因为要求方案数，那么肯定最优化剪枝不行
排序？似乎对本题求解没什么帮助
而可行性剪枝在这里可以发挥出作用
如果某个人在这局比赛后每次都赢，但是最终得分仍然低于期望得分，那么这个情况不存在，直接return
还是以三个人为例
上面的代码可以改成这样子：
void dfs(int step) {
if(step==cs+1){
int ff=1;
for(int i=1;i<=n;i++)
if(a[i]!=s[i]) ff=0;
if(ff)
ans++;
return;
}
for(int i=1;i<=n;i++){//剪枝
if(jz[n][i][step+1]*3+s[i]<a[i])//jz数组记录了总共n个人时第step场比赛后，还有几局比赛的机会（即胜利的可能）
return;
}
int x=team3[step][0],y=team3[step][1];
if(s[x]+3<=a[x]){
s[x]+=3;
dfs3(step+1);
s[x]-=3;
}
if(s[y]+3<=a[y]){
s[y]+=3;
dfs3(step+1);
s[y]-=3;
}
if(s[x]+1<=a[x]&&s[y]+1<=a[y]){
s[x]++;
s[y]++;
dfs3(step+1);
s[y]--;
s[x]--;
}
}
其他的细节比如当n2||n1时可以直接输出
还有team数组(可以再写一个test程序直接输出，不用手打)：
int team8[50][2]={{1,2},{1,3},{1,4},{1,5},{1,6},{1,7},{1,8},{2,3},{2,4},{2,5},{2,6},{2,7},{2,8},{3,4},{3,5},{3,6},{3,7},{3,8},{4,5},{4,6},{4,7},{4,8},{5,6},{5,7},{5,8},{6,7},{6,8},{7,8}};
int team7[50][2]={{1,2},{1,3},{1,4},{1,5},{1,6},{1,7},{2,3},{2,4},{2,5},{2,6},{2,7},{3,4},{3,5},{3,6},{3,7},{4,5},{4,6},{4,7},{5,6},{5,7},{6,7}};
int team6[50][2]={{1,2},{1,3},{1,4},{1,5},{1,6},{2,3},{2,4},{2,5},{2,6},{3,4},{3,5},{3,6},{4,5},{4,6},{5,6}};
int team5[50][2]={{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}};
int team4[50][2]={{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}};
int team3[50][2]={{1,2},{1,3},{2,3}};
这样大概...就可以AC了吧