[关闭]
@Junlier 2018-10-05T20:41:23.000000Z 字数 1969 阅读 1940

科比的比赛(题解)(贪心+搜索)

算法——贪心
阅读体验:https://zybuluo.com/Junlier/note/1301158

贪心+搜索

洛谷题目:P2460 [SDOI2007]科比的比赛

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

这道题其实真的不是很难的
为什么一直没有人做(其实我也是看到科比才进来的。。。

入正题吧

思路一:贪心

爆搜肯定过不了对吧
看一下题目,发现这个好大八大
再仔细看一下题目,发现给的很舒服啊
于是有一个大胆的想法:复杂度和有关,和无关
怎么说呢:

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

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

思路二:不用讲了吧

贪心都干了这么多活了,你搜索随便剪一下枝不就过了
嗯,算半个

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

剪剪剪,没了。。。

思路三:更优秀的方法?

我觉得可行:

  • 第一问你跑一个最大费用流
  • 第二问你跑一个状压dp?Maybe

应该比搜索要快吧(如果你想跑快点,反正我没打)

关于精度

题目里说是的精度保障就
然而,经过惨痛的试数据后发现要保留到小数点后12位
不然不是too short就是too long。。。

代码

我就放一个搜索+贪心的方法吧。。。
如果还不懂的讨论区问吧。。。

  1. #include<bits/stdc++.h>
  2. #define il inline
  3. #define rgt register int
  4. #define lst long long
  5. #define ldb double
  6. #define N 15
  7. #define M 100050
  8. using namespace std;
  9. const int Inf=1e9;
  10. const ldb eps=1e-10;
  11. il int read()
  12. {
  13. int s=0,m=0;char ch=getchar();
  14. while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
  15. while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  16. return m?-s:s;
  17. }
  18. int n,m;
  19. int val[M],nn[N];
  20. int Nn[N],Ans_ss;
  21. ldb Gl[N],Ans_gl;
  22. bool vis[M];
  23. struct PLAY{int id;ldb mb;}peo[M],ljl[N][N];
  24. int Calc(ldb x,ldb y)
  25. {
  26. if(abs(x-y)<=eps)return 2;
  27. else return x>y;
  28. }
  29. bool cmp(const PLAY &a,const PLAY &b)
  30. {
  31. if(Calc(a.mb,b.mb)==2)
  32. return val[a.id]>val[b.id];
  33. return a.mb>b.mb;
  34. }
  35. void Dfs(int now,ldb gl,int ss)//rival
  36. {
  37. if(now==n+1)
  38. {
  39. if(Calc(gl,Ans_gl)>0)
  40. Ans_gl=gl,Ans_ss=max(Ans_ss,ss);
  41. return;
  42. }
  43. if(Calc(gl*Gl[now],Ans_gl)==0)return;
  44. if(Calc(gl*Gl[now],Ans_gl)==2&&ss+Nn[now]<=Ans_ss)return;
  45. for(int i=1;i<=n;++i)
  46. {
  47. if(vis[ljl[now][i].id])continue;
  48. vis[ljl[now][i].id]=true;
  49. Dfs(now+1,gl*ljl[now][i].mb,ss+val[ljl[now][i].id]);
  50. vis[ljl[now][i].id]=false;
  51. }
  52. }
  53. int main()
  54. {
  55. freopen("s.in","r",stdin);
  56. n=read(),m=read();
  57. for(int i=1;i<=m;++i)val[i]=read();
  58. for(int i=1;i<=n;++i)
  59. {
  60. for(int j=1;j<=m;++j)
  61. peo[j].id=j,scanf("%lf",&peo[j].mb);
  62. sort(peo+1,peo+m+1,cmp);
  63. for(int j=1;j<=n;++j)
  64. ljl[i][j]=peo[j],nn[i]=max(nn[i],val[peo[j].id]);
  65. }Gl[n]=ljl[n][1].mb;
  66. for(int i=n-1;i>=1;--i)
  67. {
  68. Gl[i]=Gl[i+1]*ljl[i][1].mb;
  69. Nn[i]=Nn[i+1]+nn[i];
  70. }Dfs(1,1,0);
  71. printf("%.12lf\n%d\n",Ans_gl,Ans_ss);
  72. return 0;
  73. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注