即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

BZOJ 1306: [CQOI2009]match循环赛 爆搜,剪枝

编程语言 just_sort 6℃ 0评论

这里写图片描述

Input


第一行包含一个正整数n,队伍的个数。第二行包含n个非负整数,即每支队伍的得分。


Output


输出仅一行,即可能的分数表数目。保证至少存在一个可能的分数表。


Sample Input


6

5 6 7 7 8 8

Sample Output


121


HINT

N<=8

解法:

看到这题懵了,什么鬼题啊。。。。。。看了题解才知道可以爆搜。。但是需要一些剪枝优化才可以过。

1.如果剩下的比赛全赢还是不够的话 return

2.如果分数加上3或者1 超出。就不dfs

3.重磅剪枝:!! 如果搜索到当前队伍的最后一场比赛分数是可以确定的,如果不符合条件 return(记得回

溯的时候把新加的值删掉);

//BZOJ 1306

#include 
using namespace std;

struct node{
    int u, v;
}e[1005];

int n, tot, ans, a[10], b[10], s[10], last[10];

//last[i]代表队i最后比赛的场


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;
}

转载请注明:CodingBlog » BZOJ 1306: [CQOI2009]match循环赛 爆搜,剪枝

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情