Description
沫沫非常喜欢看足球赛，但因为沉迷于射箭游戏，错过了最近的一次足球联赛。此次联赛共(N)支球队参加，比赛规则如下：
(1) 每两支球队之间踢一场比赛。
(2) 若平局，两支球队各得(1)分。
(3) 否则胜利的球队得(3)分，败者不得分。
尽管非常遗憾没有观赏到精彩的比赛，但沫沫通过新闻知道了每只球队的最后总得分， 然后聪明的她想计算出有多少种可能的比赛过程。
譬如有(3)支球队，每支球队最后均积(3)分，那么有两种可能的情况：
可能性1：
| 球队 | (A) | (B) | (C) | 得分 |
|---|---|---|---|---|
| (A) | (-) | (3) | (0) | (3) |
| (B) | (0) | (-) | (3) | (3) |
| (C) | (3) | (0) | (-) | (3) |
可能性2：
| 球队 | (A) | (B) | (C) | 得分 |
|---|---|---|---|---|
| (A) | (-) | (0) | (3) | (3) |
| (B) | (3) | (-) | (0) | (3) |
| (C) | (0) | (3) | (-) | (3) |
但沫沫发现当球队较多时，计算工作量将非常大，所以这个任务就交给你了。请你计算出可能的比赛过程的数目，由于答案可能很大，你只需要输出答案对(10^9+7)取模的结果
Input
第一行是一个正整数(N)，表示一共有(N)支球队。 接下来一行(N)个非负整数，依次表示各队的最后总得分。
输入保证(20\%)的数据满足(Nle 4)，(40\%)的数据满足(Nle 6)，(60\%)的数据满足(Nle 8)，(100\%)的数据满足(3le Nle 10)且至少存在一组解。
Output
仅包含一个整数，表示答案对(10^9+7)取模的结果
Sample Input
4
4 3 6 4
Sample Output
3
Source
(Hnoi2013)
题解
很久很久做的题，先上(Dfs+)减枝，简单的搜索，不必讲解。
#include<iostream>
#include<cstdio>
using namespace std;int n,a[10],now[10],Ans;
inline void Scanf(int &x)
{
x=0;char s=getchar();
while(s<'0'||s>'9')s=getchar();
while(s>='0'&&s<='9')x=x*10+s-'0',s=getchar();
}void Dfs(int t,int T){
if(now[t]>a[t]||now[T]>a[T])return;
if(now[t]+(n-T+1)*3<a[t])return;
if(now[T]+(n-t+1)*3<a[T])return;
if(t==n){++Ans;return;}
if(T==n){int YH=a[t]-now[t];
if(YH==1){++now[t],++now[T];Dfs(t+1,t+2);--now[t],--now[T];}
if(YH==3){now[t]+=3;Dfs(t+1,t+2);now[t]-=3;}
if(YH==0){now[T]+=3;Dfs(t+1,t+2);now[T]-=3;}
return;
}
++now[t],++now[T];Dfs(t,T+1);
--now[t],--now[T];
now[t]+=3;Dfs(t,T+1);now[t]-=3;
now[T]+=3;Dfs(t,T+1);now[T]-=3;
}int main(){
int i;Scanf(n);
for(i=1;i<=n;++i)Scanf(a[i]);
Dfs(1,2),printf("%d
",Ans);
return 0;
}
正解是记忆化搜索，从目标状态往前搜索，用(Hash)记录每一种状态，具体见代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=15,maxn=1000007,inf=1000000007;
int n,num[N],tmp[N];
struct node
{
ll id;
int ans,next;
}Hash[maxn+1];
int hd[maxn+1],cnt;
ll GetHash(int nw)
{
for(int i=1;i<=n;++i) tmp[i]=num[i];
sort(tmp+1,tmp+n+1);
ll Res=0;
for(int i=1;i<=n;++i) Res=Res*27+tmp[i];//10个球队，最高比分为27
return Res*27+nw;//由于当状态相同时未比赛的队伍数必须相同，所以还要把nw也算入Hash值
}
int Find(ll id)//差询
{
int Id=id%maxn;
for(int i=hd[Id];i;i=Hash[i].next)
if(Hash[i].id==id) return Hash[i].ans;
return -1;
}
int Insert(ll id,int ans)//将新计算的值记录于Hash表
{
int YH=id%maxn;
++cnt,Hash[cnt]=(node){id,ans,hd[YH]},hd[YH]=cnt;
return ans;
}
int Dfs(int nw,int nt)//nw表示当前枚举的球队,nt表示与之比赛的球队
{
if(nw==n)
{
if(num[n]) return 0;
return 1;//初始值为0
}
if(nt>n)
{
if(num[nw]) return 0;
ll id=GetHash(nw);//计算Hash值
int YH=Find(id);//在Hash表查询次数
if(YH!=-1) return YH;//已计算
return Insert(id,Dfs(nw+1,nw+2));//记录
}
int Res=0;
if(num[nw]>=3)//与之比赛的球队赢
{
num[nw]-=3,
Res=(Res+Dfs(nw,nt+1))%inf,
num[nw]+=3;
}
if(num[nw]>=1&&num[nt]>=1)//平局
{
--num[nw],--num[nt],
Res=(Res+Dfs(nw,nt+1))%inf,
++num[nw],++num[nt];
}
if(num[nt]>=3)//当前枚举的球队赢
{
num[nt]-=3,
Res=(Res+Dfs(nw,nt+1))%inf,
num[nt]+=3;
}
return Res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&num[i]);
sort(num+1,num+n+1);//可以去掉
int Ans=Dfs(1,2);
printf("%d
",Ans);
return 0;
}