[BZOJ1306] [CQOI2009] match循环赛 (搜索)

Description

Input

　　第一行包含一个正整数n，队伍的个数。第二行包含n个非负整数，即每支队伍的得分。

Output

　　输出仅一行，即可能的分数表数目。保证至少存在一个可能的分数表。

Sample Input

6
5 6 7 7 8 8

Sample Output

121

HINT

　　N<=8

Source

Solution

　　搜索，砍树式的剪枝。当某一队算到最后一场比赛时直接算结果，每次递归前判断如果以后几场全赢分数也达不到目标分数就剪枝，如果以后几场全输都超过目标分数也剪枝

　　代码运行时间刚好10sQAQ

 #include <bits/stdc++.h>

 using namespace std;

 int n, a[], cur[], ans, d[] = {, , , };

 void DFS(int u, int v)

 {

     if(cur[u] > a[u] || cur[v] > a[v]) return;

     if(a[u] - cur[u] >  * (n - v + )) return;

     if(a[v] - cur[v] >  * (n - u + )) return;

     if(u == n)

     {

         ans++;

         return;

     }

     if(v == n)

     {

         int i = a[u] - cur[u];

         if(i >  || i == ) return;

         cur[u] += i, cur[v] += d[i];

         DFS(u + , u + );

         cur[u] -= i, cur[v] -= d[i];

         return;

     }

     cur[u] += , DFS(u, v + ), cur[u] -= ;

     cur[u]++, cur[v]++, DFS(u, v + ), cur[u]--, cur[v]--;

     cur[v] += , DFS(u, v + ), cur[v] -= ;

 }

 int main()

 {

     cin >> n;

     for(int i = ; i <= n; i++)

         cin >> a[i];

     DFS(, );

     cout << ans << endl;

     return ;

 }