题目传送门
题意:有 n 支球队,每两支球队之间都会进行一场较量,赢者积 3 分,输者积 0 分,如果平局则各积 1 分。给出每支球队的最终积分,求方案数。n≤8。
首先考虑常规搜索。直接搜索每两支球队的比赛结果,中途可以进行可行性剪枝:如果当前球队剩下的比赛全赢也不能超过目标得分则直接返回;如果当前球队已经超过了目标的分则直接返回。关于搜索的顺序,可以每次只考虑一支球队,搜索时改变第二支球队,搜完这支球队后直接检查是否合法。反映在积分矩阵上则为按行搜索。
以上的做法虽然可以通过本题,但跑得非常慢,于是考虑进一步优化。
首先,我们可以使用两层搜索嵌套的思路来实现:外层搜索考虑“当前球队”,内层搜索考虑“和其他球队如何匹配”。为了代码实现简便,这里外层搜索倒序搜索。搜索的过程中维护一个数组(具体可用 vector),表示每个球队还剩多少积分等待匹配。由于是倒序搜索,每搜一支球队一定是将积分全部耗光(否则不合法),所以可以直接从 vector 里删除最后一个元素。内层搜索时顺序考虑每一支球队,考虑和最后一支球队形成什么结果。递归时改变数组中的值,回溯时恢复即可。
有了框架,考虑如何剪枝。一个直接的剪枝与常规搜索一样,为:如果当前球队剩下的比赛全赢也达不到剩下的目标得分(因为这里数组存的是还剩多少积分等待匹配)。还可以有一个剪枝:搜索时维护当前的剩余积分之和,由于每进行一场比赛都会产生 2 或 3 分的总积分值,所以可以根据剩下的积分和以及剩下的局数进行一次剪枝。
接下来就到了这个做法最核心的地方:这个搜索可以进行记忆化。在外层搜索中,对于固定的“剩余数组”,剩余的匹配方式的方案数不变,而相同的“剩余数组”是非常容易重复计算的,比如 a→c,b−d 和 a−d,b→c 在考虑 c,d 时的剩余数组是相同的(箭头表示打败的情况)。由于记忆化的内容为一个数组,所以可以使用哈希的方式来保存。
By cxm1024, from Myth5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
| #include<bits/stdc++.h> using namespace std; const int mod=1e9+7; int hsh(vector<int> &a) { long long res=0; for(int v:a) res=(res*31+v)%mod; return res; } unordered_map<int,int> mp; int dfs_out(vector<int> &a,int sum); int dfs_in(vector<int> &a,int now,int sum) { int n=a.size(),res=0; if(a.back()>(n-1-now)*3) return 0; if(sum<(n*(n-1)/2-now)*2||sum>(n*(n-1)/2-now)*3) return 0; if(now==n-1) { vector<int> b(a.begin(),a.end()-1); return dfs_out(b,sum); } if(a[now]>0&&a.back()>0) { a[now]--,a.back()--; if(a[now]<=(n-1-1)*3) res+=dfs_in(a,now+1,sum-2); a[now]++,a.back()++; } if(a[now]>=3) { a[now]-=3; res+=dfs_in(a,now+1,sum-3); a[now]+=3; } if(a.back()>=3) { a.back()-=3; if(a[now]<=(n-1-1)*3) res+=dfs_in(a,now+1,sum-3); a.back()+=3; } return res; } int dfs_out(vector<int> &a,int sum) { if(a.empty()) return 1; int tmp=hsh(a); if(mp.count(tmp)) return mp[tmp]; return mp[tmp]=dfs_in(a,0,sum); } signed main() { freopen("history.in","r",stdin); freopen("history.out","w",stdout); int n,sum=0; cin>>n; vector<int> a; for(int i=1;i<=n;i++) { int x; cin>>x; a.push_back(x); sum+=x; } cout<<dfs_out(a,sum)<<endl; return 0; }
|