[HNOI2013]比赛

搜索 记忆化

题面

$n$个球队，两两比赛，胜得$3$分，平各得$1$分。告知每队最后得分，询问有多少种不同比赛结果。

• $n\leq10$

解析

$n\leq10$很有深意啊。反正这题不可能状压，那肯定是叫我们打记搜。

我一开始的想法是把搜索的状态设为各组当时的得分（$28^{10}$爆不了$long\ long$)。
然而这样就不能记忆化了，因处理(加)得分时不知道两个队是否比赛过,强设该状态又炸空间。

于是还是枚举每场比赛的结果吧。
当然，可以有剪枝：

• 将各组最终得分从大到小排序，然后$n对[1,n-1],(n-1)对[1,n-2],...,(2)对[1,1]$枚举比赛状态，如果发现前者分数用(扣)不完就$return$。
• 用$dp[i]$记忆化 前面比赛完的人的分数 为$i$（二十八进制数转十进制）后的方案数。（只有这样设状态才知道哪些队没比赛过）

还有值得注意的一点，$dp$数组初始值应该设为$-1$，这样才能同已经计算过、方案数为$0$的情况区分开来。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7;
map<ll,ll>dp;
ll n,pj,a[20];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il bool cmp(re ll x,re ll y){return x>y;}
il ll calc(re int x)
{
  re ll New=x,d[20];//!!!!
  fp(i,1,x) d[i]=a[i];
    sort(d+1,d+1+x);//!!!!!
  fp(i,1,x) New=New*28+d[i];//!!!!
  return New;
}
il ll dfs(re int l,re int r)
{
    re ll tot=0;
    if(a[r]>3*(r-l)) return -1;
    if(l==r)
        if(r==1) return 1;
        else
        {
            re ll now=calc(r-1);
            if(dp[now]) return dp[now];
            else return dp[now]=dfs(1,r-1);
        }
    if(a[l]>=3)
    {
        a[l]-=3;
        re ll tmp=dfs(l+1,r);if(tmp!=-1) tot+=tmp;if(tot>=mod) tot-=mod;
        a[l]+=3;
    }
    if(a[r]>=3)
    {
        a[r]-=3;
      re ll tmp=dfs(l+1,r);if(tmp!=-1) tot+=tmp;if(tot>=mod) tot-=mod;
        a[r]+=3;
    }
    if(a[l]&&a[r])
    {
        --a[l];--a[r];
        re ll tmp=dfs(l+1,r);if(tmp!=-1) tot+=tmp;if(tot>=mod) tot-=mod;
        ++a[l];++a[r];
    }
    return tot?tot:-1;
}
int main()
{
  n=gi();
  fp(i,1,n) a[i]=gi();
    sort(a+1,a+1+n,cmp);
  printf("%lld\n",dfs(1,n));
  return 0;
}