比赛 20160419x 评测结果 AAAAAAAAAA
题目名称 贿赂 最终得分 100
用户昵称 Satoshi 运行时间 0.328 s
代码语言 C++ 内存使用 0.28 MiB
提交时间 2016-04-19 16:03:36
显示代码纯文本
  1. #include <fstream>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <iomanip>
  5. #include <cstring>
  6. #define N 11
  7. using namespace std;
  8. typedef double ld;
  9. ifstream in("bribe.in");
  10. ofstream out("bribe.out");
  11. int n,K;
  12. ld A;
  13. ld a[N]={0},b[N]={0},add[N]={0},win[N]={0},fail[N]={0};
  14. bool l[N]={0};
  15. int top=0;
  16. ld ans=0;
  17. void print(ld x,int y){out<<setprecision(y)<<std::fixed<<x<<endl;}
  18. ld update()
  19. {
  20. int i,tolo=0;
  21. ld sum=1;
  22. ld solo=0;
  23. for(i=1;i<=n;i++)
  24. {
  25. if(l[i])
  26. {
  27. sum*=win[i];
  28. tolo++;//总共有多少人投了支持票
  29. }
  30. else
  31. {
  32. sum*=fail[i];
  33. solo+=a[i];
  34. }
  35. }
  36. if(tolo<=n/2)sum*=(A/(A+solo));//干掉那些人
  37. memset(l,0,sizeof(l));
  38. return sum;
  39. }
  40. void fuck()
  41. {
  42. int i,temp,cnt=0;
  43. ld sum=0;
  44. for(i=1;i<=n;i++)
  45. {
  46. win[i]=b[i]+add[i];
  47. if(win[i]>10)win[i]=10;
  48. win[i]/=10.0;
  49. fail[i]=1-win[i];
  50. //out<<win[i]<<' '<<fail[i]<<' '<<endl;
  51. }
  52. for(i=0;i<(1<<n);i++)
  53. {
  54. temp=i;
  55. cnt=0;
  56. while(temp)
  57. {
  58. l[++cnt]=temp%2;
  59. temp=temp>>1;
  60. }
  61. sum+=update();
  62. }
  63. if(sum>ans)ans=sum;
  64. }
  65. void DFS(int tot,int pos)//糖果已经给了tot个人,位置指针指向pos
  66. {
  67. if(tot>K)return ;
  68. if(pos==n+1)
  69. {
  70. if(tot==K)fuck();
  71. return ;
  72. }
  73. else
  74. {
  75. for(int i=0;i<=K-tot;i++)
  76. {
  77. if(b[pos]+i>10.0)return ;
  78. add[pos]=i;
  79. DFS(i+tot,pos+1);
  80. add[pos]=0;
  81. }
  82. }
  83. }
  84. void read()
  85. {
  86. int i;
  87. in>>n>>K>>A;
  88. for(i=1;i<=n;i++)
  89. {
  90. in>>a[i]>>b[i];
  91. b[i]/=10.0;
  92. }
  93. }
  94. void work()
  95. {
  96. DFS(0,1);
  97. }
  98. int main()
  99. {
  100. //int start,end;
  101. //start=clock();
  102. read();
  103. work();
  104. print(ans,6);
  105. //end=clock();
  106. //out<<end-start<<endl;
  107. return 0;
  108. }