[BZOJ3139][HNOI2013]比赛(搜索)
3139: [Hnoi2013]比赛
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 1439 Solved: 719
[Submit][Status][Discuss]Description
沫沫非常喜欢看足球赛,但因为沉迷于射箭游戏,错过了最近的一次足球联赛。此次联 赛共N支球队参加,比赛规则如下:
(1) 每两支球队之间踢一场比赛。 (2) 若平局,两支球队各得1分。
(3) 否则胜利的球队得3分,败者不得分。
尽管非常遗憾没有观赏到精彩的比赛,但沫沫通过新闻知道了每只球队的最后总得分, 然后聪明的她想计算出有多少种可能的比赛过程。
譬如有3支球队,每支球队最后均积3分,那么有两种可能的情况:
可能性1 可能性2
球队 A B C 得分 球队 A B C 得分
A - 3 0 3 A - 0 3 3
B 0 - 3 3 B 3 - 0 3
C 3 0 - 3 C 0 3 - 3
但沫沫发现当球队较多时,计算工作量将非常大,所以这个任务就交给你了。请你计算 出可能的比赛过程的数目,由于答案可能很大,你只需要输出答案对109+7取模的结果Input
第一行是一个正整数N,表示一共有N支球队。接下来一行N个非负整数,依次表示各队的最后总得分。
输入保证20%的数据满足N≤4,40%的数据满足N≤6,60%的数据满足N≤8,100%的数据满足3≤N≤10且至少存在一组解。
Output
仅包含一个整数,表示答案对10^9+7取模的结果
Sample Input
4
4 3 6 4Sample Output
3HINT
Source
暴搜肯定过不了,观察发现如果一个人和其他所有人的胜负都定下来后,问题就变成了规模为n-1的子问题,这个可以通过排序压位加Hash存在map里记忆化。注意一个人的所有胜负确定之前是不能作记忆化判断的。
还有一个剪枝(程序里没加),哪个大就让哪个输,这样会快一些。
#include<map>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
typedef long long ll;
using namespace std; const int N=,mod=;
int n,a[N],tmp[N];
map<ll,int>mp[N];
ll gethash(int x){ ll res=; rep(i,x,n) res=res*+tmp[i]; return res; } int dfs(int x,int k){
ll t;
if (x==n) return (a[x]==);
if (k>n) return (a[x]!=) ? : dfs(x+,x+);
if (k==x+){
rep(i,x,n) tmp[i]=a[i];
sort(tmp+x,tmp+n+); int s=*(n-x);
if (tmp[x]<-s || tmp[n]>s) return ;
t=gethash(x);
if (mp[x].count(t)) return mp[x][t];
}
int res=;
a[k]-=; res=(res+dfs(x,k+))%mod; a[k]+=;
a[x]-=; res=(res+dfs(x,k+))%mod; a[x]+=;
a[x]--; a[k]--; res=(res+dfs(x,k+))%mod; a[x]++; a[k]++;
if (k==x+) mp[x][t]=res;
return res;
} int main(){
freopen("match.in","r",stdin);
freopen("match.out","w",stdout);
scanf("%d",&n);
rep(i,,n) scanf("%d",&a[i]);
sort(a+,a+n+);
printf("%d\n",dfs(,));
return ;
}
最新文章
- ViewPager+Fragment取消预加载(延迟加载)(转)
- HDU 5228
- iOS:集成ijkplayer视频直播
- sqlite 批量插入, 重复插入(更新)
- HTML Music Entities/音乐符号
- php数组使用技巧及操作总结
- linux+nginx+mysql+php高性能服务器搭建
- uml系列(八)——部署图与构件图
- HTML5 File接口(在web页面上使用文件)
- docker 添加国内源
- java中的Collection集合类
- 如何判断页面是qq浏览器还是微信浏览器打开
- servlet获取多个同名参数
- Java 获取当前项目所在服务器的 IP 地址
- codeforces 777C
- day17(tomcat的安装,HTTP)
- Android-Kotlin-配置/入门
- Web打印控件Lodop实现证件套打
- Docker企业级仓库Harbor的安装配置与使用
- 跟我学Makefile(三)
热门文章
- [NOIP2003]栈 题解(卡特兰数)
- 【IDEA】IDEA设置新建文件的模板
- 【Python学习】字符编码
- React 16 源码瞎几把解读 【一】 从jsx到一个react 虚拟dom对象
- sql server 2008 r2 产品密钥
- angular项目中使用jQWidgets
- FAQ1: 列表索引和切片问题
- C/C++——#和##操作符
- ActiveMQ-Prefetch机制和constantPendingMessageLimitStrategy
- CentOS7.4 安装 oracle12c