自动搬运

查看原文

来自洛谷，原作者为

	eternal风度 **

搬运于2025-08-24 21:37:56，当前版本为作者最后更新于2018-10-05 20:34:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

贪心+搜索

也可以贪心+网络流+状压dp

这道题其实真的不是很难的

为什么一直没有人做（其实我也是看到科比才进来的。。。）

照例，想打一波广告：eternal风度的博客 欢迎来踩

同步发表于：科比的比赛(题解)(贪心+搜索)

入正题吧

思路一：贪心

爆搜肯定过不了对吧

看一下题目，发现这个$m$好大八大

再仔细看一下题目，发现$n$给的很舒服啊

于是有一个大胆的想法：复杂度和$n$有关，和$m$无关

怎么说呢：我们可以发现我们再怎么打，一场里面最多有9个球员之前打过对吧，也就是说，如果我们把每一场的球员按照胜率排序，那么和答案有关的最多就只有10个人对吧

所以我们考虑对每一场按照胜率把球员排序（能力值为第二关键字），一下子省去好多。。。

思路二：不用讲了吧

贪心都干了这么多活了，你搜索随便剪一下枝不就过了

嗯，算半个$A^*$吗

把每场比赛以后能打出的最大胜率预处理出来

把每场比赛以后能打到的最大能力值预处理出来

剪剪剪

没了

思路三：更优秀的方法？

我觉得可行：

第一问你跑一个最大费用流

第二问你跑一个状压dp？Maybe

应该比搜索要快吧（如果你想跑快点，反正我没打）

关于精度

题目里说是$1e-10$的精度保障就$ojbk$

然而，经过惨痛的试数据后发现要保留到小数点后12位

不然不是too short就是too long。。。

代码

我就放一个搜索+贪心的方法吧。。。

如果还不懂的讨论区问吧。。。

或者私信我。。。（讨论区@不了看不到。。。）

#include<bits/stdc++.h>
#define il inline
#define rgt register int
#define lst long long
#define ldb double
#define N 15
#define M 100050
using namespace std;
const int Inf=1e9;
const ldb eps=1e-10;
il int read()
{
	int s=0,m=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
	while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return m?-s:s;
}

int n,m;
int val[M],nn[N];
int Nn[N],Ans_ss;
ldb Gl[N],Ans_gl;
bool vis[M];
struct PLAY{int id;ldb mb;}peo[M],ljl[N][N];
int Calc(ldb x,ldb y)
{
	if(abs(x-y)<=eps)return 2;
	else return x>y;
}

bool cmp(const PLAY &a,const PLAY &b)
{
	if(Calc(a.mb,b.mb)==2)
		return val[a.id]>val[b.id];
	return a.mb>b.mb;
}

void Dfs(int now,ldb gl,int ss)//rival
{
	if(now==n+1)
	{
		if(Calc(gl,Ans_gl)>0)
			Ans_gl=gl,Ans_ss=max(Ans_ss,ss);
		return;
	}
	if(Calc(gl*Gl[now],Ans_gl)==0)return;
	if(Calc(gl*Gl[now],Ans_gl)==2&&ss+Nn[now]<=Ans_ss)return;
	for(int i=1;i<=n;++i)
	{
		if(vis[ljl[now][i].id])continue;
		vis[ljl[now][i].id]=true;
		Dfs(now+1,gl*ljl[now][i].mb,ss+val[ljl[now][i].id]);
		vis[ljl[now][i].id]=false;
	}
}

int main()
{
	freopen("s.in","r",stdin);
	n=read(),m=read();
	for(int i=1;i<=m;++i)val[i]=read();
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
			peo[j].id=j,scanf("%lf",&peo[j].mb);
		sort(peo+1,peo+m+1,cmp);
		for(int j=1;j<=n;++j)
			ljl[i][j]=peo[j],nn[i]=max(nn[i],val[peo[j].id]);
	}Gl[n]=ljl[n][1].mb;
	for(int i=n-1;i>=1;--i)
	{
		Gl[i]=Gl[i+1]*ljl[i][1].mb;
		Nn[i]=Nn[i+1]+nn[i];
	}Dfs(1,1,0);
	printf("%.12lf\n%d\n",Ans_gl,Ans_ss);
	return 0;
}