Input第贰行李包裹蕴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 }