bzoj|bzoj 1306 [CQOI2009]match循环赛
Description
Input
第一行包含一个正整数n，队伍的个数。第二行包含n个非负整数，即每支队伍的得分。
Output
输出仅一行，即可能的分数表数目。保证至少存在一个可能的分数表。
Sample Input
【bzoj|bzoj 1306 [CQOI2009]match循环赛】6
5 6 7 7 8 8
Sample Output
121
;
-) 伐开心。今天有人说汉子的外表下藏着颗玻璃心。。
尼玛。。简单搜索 写懵逼了。
搜索：搜每一个队伍的每一场比赛的情况
剪枝其实很高端。
1.如果剩下的比赛全赢还是不够的话 return
2.如果分数加上3或者1 超出。就不dfs
3.重磅剪枝：！！ 如果搜索到当前队伍的最后一场比赛分数是可以确定的，如果不符合条件 return（记得回溯的时候把新加的值删掉）；
#include
#include
#include
using namespace std;
//by mars_ch
struct data
{
int u,v;
}e[100005];
int n,tot,ans;
int a[10],b[10];
int last[10005],s[10];
void dfs(int x)
{
if(x>tot)
{
for(int i=1;
i<=n;
i++)
{
if(a[i] != s[i]) return;
}
ans++;
return;
}
int u=e[x].u,v=e[x].v;
if((last[u]-x+1)*3+a[u]return;
//都赢也不可以
if((last[v]-x+1)*3+a[v]return;
if(last[u] == x)
{
if(a[u]+3 == s[u])
{
a[u]+=3;
if(a[v]<=s[v]) dfs(x+1);
a[u]-=3;
}
else if(a[u]+1==s[u])
{
a[u]+=1,a[v]+=1;
if(a[v] <= s[v]) dfs(x+1);
a[u]-=1,a[v]-=1;
}
else if(a[u]==s[u])
{
a[v]+=3;
if(a[v] <= s[v]) dfs(x+1);
a[v]-=3;
}
return;
}
if(a[u]+3<=s[u])
{
a[u]+=3;
dfs(x+1);
a[u]-=3;
}
if(a[u]+1<=s[u] && a[v]+1<=s[v])
{
a[u]+=1,a[v]+=1;
dfs(x+1);
a[u]-=1,a[v]-=1;
}
if(a[u]<=s[u] && a[v]+3<=s[v])
{
a[v]+=3;
dfs(x+1);
a[v]-=3;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;
i<=n;
i++)
{
scanf("%d",&s[i]);
}
for(int i=1;
i<=n;
i++)
{
for(int j=i+1;
j<=n;
j++)
{
e[++tot].u=i,e[tot].v=j;
}
last[i]=tot;
//每队最后比赛的场
}
dfs(1);
printf("%d\n",ans);
return 0;
}
/*
8
7 7 8 8 9 9 10 10
*/ 推荐阅读
- 【BZOJ】4316:|【BZOJ】4316: 小C的独立集 静态仙人掌
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- 线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN
- bzoj|Bzoj3817:Sum
- BZOJ|BZOJ2763[JLOI2011]飞行路线【分层图最短路】
- BZOJ3817（Sum（类欧几里得））
- 类欧几里得|bzoj2987 Earthquake 类欧几里得
- 题解|[BZOJ3817] Sum
- bzoj2712 -- 类欧几里得算法
- Bzoj|[BZOJ2187][fraction][类欧几里得算法]