[HNOI2013]比赛-白红宇

[HNOI2013]比赛

阅读量：5149 次

发布时间：2019-06-13

本文共 1936 字，大约阅读时间需要 6 分钟。

题面

\(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
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #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
           
            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;}