模仿爆搜

www.27111.com 1Input第贰行李包裹蕴1个正整数n,队伍容貌的个数。第贰行包含n个非负整数,即每支军队的得分。Output输出仅一行,即也许的分数表数目。保险最少存在贰个大概的分数表。Sample
Input

6
5 6 7 7 8 8

Sample Output

121

Hint

N<=8

 

其一肯定正是爆搜吧,因为数量比较小。

不过数量13分神奇

枚举每场竞赛,枚举编号较小的一队的结果,相应的较大的也能够生产结果 
www.27111.com,当有某一队剩余比赛全赢也比给定分数低就剪枝 
当有某一队当下比分超越给定分数也剪枝 
假设您把那俩个剪枝加上,然后交给,你就会神奇的发现


为啥照旧狂T???


本人要么too naive,依旧被极限数据卡了。。 
于是要在加贰个,当这么些队容是和尾声一支部队比赛的时候,只要一种答案,若是和分数相差0,3,1时就搜剩下的一个应和的境况,相差2就剪枝 
。。。我以为这个优化毫无卵用,然而TM居然是有用的。。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 
 8 const int stard[4]={3,1,0,0};
 9 
10 int a[17],b[17],n,ans;
11 
12 void dfs(int x,int y)
13 {
14     if (b[x]>a[x]) return ;
15     if (b[x]+(n-y+1)*3<a[x]) return ;
16     if (n==x)
17     {
18         ans++;
19         return;
20     }
21     if (y==n)
22     {
23         int t=a[x]-b[x];
24         if (t==2) return;
25         b[y]+=stard[t];
26         dfs(x+1,x+2);
27         b[y]-=stard[t];
28     }
29     else
30     {
31         b[x]+=3;dfs(x,y+1);b[x]-=3;
32         b[y]+=3;dfs(x,y+1);b[y]-=3;
33         b[x]++,b[y]++;dfs(x,y+1);b[x]--,b[y]--;
34     }
35 }
36 int main()
37 {
38     scanf("%d",&n);
39     for (int i=1;i<=n;i++)
40         scanf("%d",&a[i]);
41     dfs(1,2);
42     printf("%d",ans);        
43 }

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注