JZOJ 4.15 1110——CQOI2009循环赛【dfs】【hash判重】

本文主要是介绍JZOJ 4.15 1110——CQOI2009循环赛【dfs】【hash判重】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

n支队伍打比赛，每两支队伍恰好比赛一场。平局时各得1分，而有胜负时胜者3分，负者0分。
假设三支队伍得分分别为3, 3, 3，则可能有两种情况：
队伍 A B C 得分
A - 3 0 3
B 0 - 3 3
C 3 0 - 3

队伍 A B C 得分
A - 0 3 3
B 3 - 0 3
C 0 3 - 3

给出n支队伍的最终得分（即所有比赛均已结束），统计有多少种可能的分数表。

Input

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

Output

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

Sample Input

样例输入1：
3
3 3 3
样例输入2：
2
0 3
样例输入3：
3
4 1 2
样例输入4：
6
5 6 7 7 8 8

Sample Output

样例输出1：
2
样例输出2：
1
样例输出3：
1
样例输出4：
121

88分方法：

剪枝：
1.如果当前枚举的已经比要求的数大，则退出
2.如果枚举到这里，后面的题全队都小于目标分数，退出
3.如果枚举到倒数第二个，与目标分数的差不为3或0或1，则退出
如果都达到了目标分数，则ans++
如果没到，则枚举三种情况：
①x队赢+3,y队输+0
②x队输+0，y队赢+3
③打平，x队和y队都加1
（Tips：dfs后要回溯）

88分代码如下：

#include<cstdio>
using namespace std;
const int f[]={3,1,0,0};
int n,a[9],ans,p[9];
void dfs(int x,int y)
{if(p[x]>a[x])return;if(p[x]+(n-y+1)*3<a[x])return;if(x==n){   ans++;return;}if(y==n){int tmp=a[x]-p[x];if (tmp==2||tmp>3) return;p[y]+=f[tmp];dfs(x+1,x+2);p[y]-=f[tmp];}else{p[x]+=3;dfs(x,y+1);p[x]-=3;p[y]+=3;dfs(x,y+1);p[y]-=3;p[x]++; p[y]++;dfs(x,y+1);p[x]--;p[y]--;}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);dfs(1,2);printf("%d\n",ans);return 0;
}

100分大法来了！！

其实其思想与上诉差不多，主要是加了一个Hash判重，Hash判重是这题最有效的剪枝。

100分代码如下：

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<map>
using namespace std;
const int N=15;
int n,a[N],ans,tmp[N];
map<long long,int>f[N];
int pc(int r,int p,int x);
int dfs(int r)
{if (r==n)return (!a[n]);tmp[0]=0;for (int i=r;i<=n;++i) tmp[++tmp[0]]=a[i];sort(tmp+1,tmp+tmp[0]+1);long long h=0;for (int i=1;i<=tmp[0];++i) h=h*29+tmp[i];if (f[r].find(h)!=f[r].end()) return f[r][h];else return f[r][h]=pc(r+1,a[r],r);
}int pc(int x,int p,int r)
{if (x>n){if (!p)return dfs(r+1);else return 0;}if ((n-x+1)*3<p)return 0;int u=0;if (a[x]>=3){a[x]-=3;u+=pc(x+1,p,r);a[x]+=3;}if (p>=1&&a[x]>=1){a[x]--;u+=pc(x+1,p-1,r);a[x]++;}if (p>=3) u+=pc(x+1,p-3,r);return u;
}int main (){scanf ("%d",&n);for (int i=1;i<=n;++i)scanf("%d",&a[i]);sort(a+1,a+n+1);printf("%d",dfs(1));return 0;
}