P3230 [HNOI2013]比赛

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<map>
 5 
 6 using namespace std;
 7 
 8 struct node
 9 {
10     int a[12];//a[0]表示当前在搜索哪个队伍，a[1]~a[n]表示目前队伍剩余得分。 
11     node()
12     {
13         memset(a,0,sizeof(a));
14     }
15 }st;
16 
17 map <long long,int>hash;
18 const int p=1000000007;
19 int n,ying,ping;
20 
21 long long geth(node x)
22 {
23     long long ret=0;
24     for(int i=0;i<=n;i++)ret=ret*28+x.a[i];//一个队最多得27分。 
25     return ret;
26 }
27 
28 int dfs(int i,node now,int win,int low)//now.a[0]与i比赛 
29 {
30     if((win>ying)||(low>ping))return -1;
31     if(now.a[0]==n) //已经是最后一个队，比赛还没结束，那么此状态不可行 
32     {
33         return -1;
34     }
35     if(now.a[now.a[0]]>3*(n-i+1))//即使now.a[0]之后全赢也不满足now，也不可行 
36     {
37         return -1;
38     }
39     if(i>n&&now.a[now.a[0]]==0)
40     {
41         now.a[0]++;
42         sort(now.a+1,now.a+1+n);//顺序不影响 
43         if(hash[geth(now)])return hash[geth(now)];
44         else
45         {
46             hash[geth(now)]=dfs(now.a[0]+1,now,win,low);
47             return hash[geth(now)];
48         } 
49     }
50     int id=now.a[0],tem,ans=0;
51     if(now.a[id]>=3)
52     {
53         now.a[id]-=3;
54         tem=dfs(i+1,now,win+1,low);
55         if(tem!=-1)ans=(ans+tem)%p;
56         now.a[id]+=3;
57     }
58     if(now.a[id]&&now.a[i])
59     {
60         now.a[id]--;
61         now.a[i]--;
62         tem=dfs(i+1,now,win,low+1);
63         if(tem!=-1)ans=(ans+tem)%p;
64         now.a[id]++;
65         now.a[i]++;
66     }
67     if(now.a[i]>=3)
68     {
69         now.a[i]-=3;
70         tem=dfs(i+1,now,win+1,low);
71         if(tem!=-1)ans=(ans+tem)%p;
72         now.a[i]+=3;
73     }
74     if(!ans)ans=-1;
75     if(i==id+1)hash[geth(now)]=ans;
76     return ans;
77 } 
78 
79 
80 int main()
81 {
82     scanf("%d",&n);
83     for(int i=1;i<=n;i++)scanf("%d",&st.a[i]);
84     sort(st.a+1,st.a+1+n);
85     int sum=0;
86     for(int i=1;i<=n;i++)sum+=st.a[i];
87     ping=3*n*(n-1)/2-sum;//剪枝：求出平了几局，赢了几局（鸡兔同笼）。 
88     ying=sum-n*(n-1);
89     node tem;
90     tem.a[0]=n;
91     hash[geth(tem)]=1; //初始化。搜完第n个队伍，各个队伍的得分都为零，这种情况下答案为1。 
92     st.a[0]=1;
93     int iss=dfs(2,st,0,0);
94     printf("%d\n",iss);
95     return 0;
96 }