首页 > 代码库 > 【搜索】【剪枝】bzoj1306 [CQOI2009]match循环赛
【搜索】【剪枝】bzoj1306 [CQOI2009]match循环赛
dfs+剪枝*4（通过得很勉强）:
1、只枚举一半的比赛，另一半直接得出。
2、处理前缀和，若大于目标得分则剪枝
3、前缀和加上若接下来全胜的得分 仍小于 目标得分，则剪枝。
4、枚举到每个人的最后一场比赛时直接用 目标得分-前缀和 计算出最后一场的应得分。
Code还是很简单的:
#include<cstdio>using namespace std;const int f[]={3,1,0,0};int n,a[9],ans,Pre[9];void dfs(int x,int y){ if(Pre[x]>a[x])return; if(Pre[x]+(n-y+1)*3<a[x])return; if(x==n){ans++;return;} if(y==n) { int tmp=a[x]-Pre[x]; if(tmp==2)return; Pre[y]+=f[tmp]; dfs(x+1,x+2); Pre[y]-=f[tmp]; }else{ Pre[x]+=3;dfs(x,y+1);Pre[x]-=3; Pre[y]+=3;dfs(x,y+1);Pre[y]-=3; Pre[x]++;Pre[y]++;dfs(x,y+1);Pre[x]--;Pre[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;}
【搜索】【剪枝】bzoj1306 [CQOI2009]match循环赛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。