题解：P2460 [SDOI2007] 科比的比赛

· · 题解

题解

分析

科比需要打 m 场比赛，即他需要跟 m 人中的 n 个单挑。

看到 m 非常大，不可能一个一个试，我们可以采用贪心策略。

既然只要跟其中 n 个人单挑，那排序把胜率最高的 n 个挑出来不就可以了吗。

但是同一个人不能打两场比赛，排序会破坏对手的顺序，所以还需要建立一个结构体存储对手信息，如下：

struct node{
    int id;//对手编号
    double v;//获胜概率
};

现在我们把 n\times m 的范围缩小到了 n\times n，而 n 的范围非常小，尝试 DFS 解决。

int maxs;      //记录最大和
double maxp=-1;//记录最大概率
bool vis[N];   //记录每个对手是否单挑过

//x:   当前比赛
//p:   当前获胜概率
//sum: 当前能力值之和
void dfs(int x,double p,int sum){
    if(x>n){//结束条件
        if(maxp<p){//搜到获胜概率更大的情况
            maxp=p;//更新概率
            maxs=sum;//更新和
        }
        else if(maxp==p){//有相同概率时
            maxs=max(sum,maxs);
        }
        return;
    }

    for(int i=1;i<=n;i++){

        if(vis[a[x][i].id])continue;
        //跳过已经打过的
        vis[a[x][i].id]=1;
        //记录
        dfs(x+1,p*a[x][i].v,sum+s[a[x][i].id]);
        //递归下一场比赛
        vis[a[x][i].id]=0;
        //回溯
    }
    return;
}

那么不出所料 TLE 了。

在搜索时，如果当前概率已经小于搜到的最好结果时，因为获胜概率小于 1，所以没必要再搜下去，可以剪枝优化。

代码如下：

if(p<maxp)return;//剪枝

现在就可以过了。

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100005;

struct node{
    int id;//对手编号
    double v;//获胜概率
}a[12][N];//a[i][j]表示第i场比赛第j个人

int n,m;
int s[N];//能力

int maxs;      //记录最大和
double maxp=-1;//记录最大概率
bool vis[N];   //记录每个对手是否单挑过

//x:   当前比赛
//p:   当前获胜概率
//sum: 当前能力值之和
void dfs(int x,double p,int sum){
    if(x>n){//结束条件
        if(maxp<p){//搜到获胜概率更大的情况
            maxp=p;//更新概率
            maxs=sum;//更新和
        }
        else if(maxp==p){//有相同概率时
            maxs=max(sum,maxs);
        }
        return;
    }

    for(int i=1;i<=n;i++){

        if(vis[a[x][i].id])continue;
        //跳过已经打过的
        vis[a[x][i].id]=1;
        //记录
        dfs(x+1,p*a[x][i].v,sum+s[a[x][i].id]);
        //递归下一场比赛
        vis[a[x][i].id]=0;
        //回溯
    }
    return;
}

bool cmp(node a1,node a2){
    if(a1.v==a2.v)return s[a1.id]>s[a2.id];
    //概率相等按能力降序排序
    return a1.v>a2.v;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>s[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j].v;
            a[i][j].id=j;//记录
        }
        sort(a[i]+1,a[i]+m+1,cmp);//每场比赛排一次序
    }

    dfs(1,1,0);

    printf("%.12lf\n",maxp);//感谢各位大佬提醒保留12位
    cout<<maxs<<endl;
    return 0;
}

其他注意事项：

DFS 只能从第一场比赛开始搜，从后往前会 WA。

c++ 的 double 足够强大，不需要开 long double，但开了更精确。

一定要保留 12 位，而且只能保留 12 位，多了少了都 WA。

代码我写得比较通俗，希望可以对你 AC 有帮助。

既然你都看到这了，给你张图奖励一下：

致敬科比。