比赛(match)
龙卷风
·
2019-08-23 07:50:07
·
个人记录
题目
Description
沫沫非常喜欢看足球赛，但因为沉迷于射箭游戏，错过了最近的一次足球联赛。此次联赛共N 支球队参加，比赛规则如下：
(1) 每两支球队之间踢一场比赛。
(2) 若平局，两支球队各得1 分。
(3) 否则胜利的球队得3 分，败者不得分。
尽管非常遗憾没有观赏到精彩的比赛，但沫沫通过新闻知道了每只球队的最后总得分，然后聪明的她想计算出有多少种可能的比赛过程。譬如有3 支球队，每支球队最后均积3 分，那么有两种可能的情况：
Clipboard Image.png
但沫沫发现当球队较多时，计算工作量将非常大，所以这个任务就交给你了。请你计算出可能的比赛过程的数目，由于答案可能很大，你只需要输出答案对109+7 取模的结果。
Input
输入文件第一行是一个正整数N，表示一共有N支球队。接下来一行N个非负整数，依次表示各队的最后总得分。输入保证20%的数据满足N≤4，40%的数据满足N≤6，60%的数据满足N≤8，100%的数据满足3≤N≤10且至少存在一组解。
Output
仅包含一个整数，表示答案对109+7取模的结果。
Sample Input 1
4
4 3 6 4
Sample Output 1
3
思路
1.dfs搜索
2.用hash记忆化搜索;
代码
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=10000007,inf=1000000007;
struct node
{
long long id;
int ans,nx;
};
int n,i,ans,len,s,j,tmp,a[28],t[28],head[maxn+1];
long long c[11];
node f[maxn+1];
int insert(long long id,int ans)
{
len++;
f[len].nx=head[id%maxn];
head[id%maxn]=len;
f[len].ans=ans;
f[len].id=id;
return ans;
}
int find(long long p)
{
int i;
i=head[p%maxn];
while(i>0)
{
if(f[i].id==p)return f[i].ans;
i=f[i].nx;
}
return -1;
}
void A(int l,int r)
{
int i,j,x,y;
i=l;j=r;x=t[(i+j)/2];
while(i<=j)
{
while(t[i]x)j--;
if(i<=j)
{
y=t[i];t[i]=t[j];t[j]=y;
i++;j--;
}
}
if(i
}
long long get_state(int now)
{
long long p=0;
for(int i=1;i<=n;i++)t[i]=a[i];
A(1,n);
p=0;
for(int i=1;i<=n;i++)
p=p*27+t[i];
return p*27+now;
}
int dfs(int now,int nx)//now当前考虑的队伍,nx,与之比赛的队伍;
{
int ans,k;
long long p;
if(now==n)
{
if(a[now]==0)return 1;
else return 0;
}
if(nx>n)
{
if(a[now]>0)return 0;
p=get_state(now);
k=find(p);
if(k!=-1)return k;
else return insert(p,dfs(now+1,now+2));
}
ans=0;
if(a[now]>=3)
{
a[now]=a[now]-3;
ans=(ans+dfs(now,nx+1))%inf;
a[now]=a[now]+3;
}
if(a[now]>=1&&(a[nx]>=1))
{
a[now]=a[now]-1;a[nx]=a[nx]-1;
ans=(ans+dfs(now,nx+1))%inf;
a[now]=a[now]+1;a[nx]=a[nx]+1;
}
if(a[nx]>=3)
{
a[nx]=a[nx]-3;
ans=(ans+dfs(now,nx+1))%inf;
a[nx]=a[nx]+3;
}
return ans;
}
int main()
{
cin>>n;
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i
{
for(j=i+1;j<=n;j++)
{
if(a[i]>a[j])
{
tmp=a[i];a[i]=a[j];a[j]=tmp;
}
}
}
ans=dfs(1,2);
cout<
return 0;
}
