P2460 [SDOI2007] 科比的比赛 题解

题目传送门。

感觉题目有那么一点点的黑科比的意思。。。

思路：贪心+搜索。

56 行清新可爱代码，删快读快输后 42 行。

该说不说，水紫一道，建议评绿。

题意

形式化题面不好描述，所以去看原题描述吧。

思路

首先，n 很小，考虑搜索。

然后根据贪心策略，每一轮优先选择概率大的，同概率的选能力大的，这样就可以剪枝了。

具体剪枝方法就是，在每一轮都判断一下，如果乘上后面最大的概率，都劣于当前记录的最优答案，是则直接返回。

这里用后缀积与后缀和维护一下就好了。

然后就能过了，时间复杂度 O(\footnotesize\texttt{能过}\normalsize)。（众所周知带剪枝的搜索的时间复杂度都不好分析）

具体见代码，带注释。

AC 代码

#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
typedef long double ld; // 为避免精度问题，开 long double
#define int long long
int in() // 快输
{
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
void out(int x) // 快读
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
const int N=20,M=1e5+10;
int ability[M]; // 能力值
struct line // 每一行定义一个结构体
{
    int id;ld win; // 第几个人；赢的概率
    bool operator<(const line a)const{return win>a.win||(win==a.win&&ability[id]>ability[a.id]);} // 自定义比较规则
};
vector<line>inning[N];int n,m;
int maxa[N];ld maxp[N]; // 后缀能力值和，后缀概率积
bool vis[M]; // 当前人选过没有
ld ansp;int ans; // 当前最优答案
void dfs(int i,ld p,int sum)
{
    if(i==n+1){if(p>ansp||(p==ansp&&sum>ans))ansp=p,ans=sum;return;} // 记录答案
    if(p*maxp[i]<ansp||(p*maxp[i]==ansp&&sum+maxa[i]<=ans))return; // 比当前记录的最优的还要劣
    for(auto [id,winp]:inning[i])if(!vis[id])vis[id]=true,dfs(i+1,p*winp,sum+ability[id]),vis[id]=false;
}
signed main()
{
    n=in(),m=in(),maxp[n+1]=1;
    for(int i=1;i<=m;i++)ability[i]=in();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            ld p;scanf("%Lf",&p);
            inning[i].push_back((line){j,p});
        }
        sort(inning[i].begin(),inning[i].end()); // 按概率排序，能力值为第二关键字
    }
    for(int i=n;i>=1;i--)maxa[i]=maxa[i+1]+ability[inning[i][0].id],maxp[i]=maxp[i+1]*inning[i][0].win; // 后缀和，后缀积
    dfs(1,1,0);
    printf("%.12Lf\n",ansp),out(ans); // 输出答案
    return 0;
}

后记

致敬伟大的已故篮球运动员 Kobe Bean Bryant Cox，一个由后天努力锻造出的天生杀手黑曼巴。

紫金飞侠成绝响，世间再无黑曼巴！