比赛 |
20160419x |
评测结果 |
AAAAAAAAAA |
题目名称 |
贿赂 |
最终得分 |
100 |
用户昵称 |
Satoshi |
运行时间 |
0.328 s |
代码语言 |
C++ |
内存使用 |
0.28 MiB |
提交时间 |
2016-04-19 16:03:36 |
显示代码纯文本
- #include <fstream>
- #include <algorithm>
- #include <cmath>
- #include <iomanip>
- #include <cstring>
- #define N 11
- using namespace std;
- typedef double ld;
- ifstream in("bribe.in");
- ofstream out("bribe.out");
- int n,K;
- ld A;
- ld a[N]={0},b[N]={0},add[N]={0},win[N]={0},fail[N]={0};
- bool l[N]={0};
- int top=0;
- ld ans=0;
- void print(ld x,int y){out<<setprecision(y)<<std::fixed<<x<<endl;}
- ld update()
- {
- int i,tolo=0;
- ld sum=1;
- ld solo=0;
- for(i=1;i<=n;i++)
- {
- if(l[i])
- {
- sum*=win[i];
- tolo++;//总共有多少人投了支持票
- }
- else
- {
- sum*=fail[i];
- solo+=a[i];
- }
- }
- if(tolo<=n/2)sum*=(A/(A+solo));//干掉那些人
- memset(l,0,sizeof(l));
- return sum;
- }
- void fuck()
- {
- int i,temp,cnt=0;
- ld sum=0;
- for(i=1;i<=n;i++)
- {
- win[i]=b[i]+add[i];
- if(win[i]>10)win[i]=10;
- win[i]/=10.0;
- fail[i]=1-win[i];
- //out<<win[i]<<' '<<fail[i]<<' '<<endl;
- }
-
- for(i=0;i<(1<<n);i++)
- {
- temp=i;
- cnt=0;
- while(temp)
- {
- l[++cnt]=temp%2;
- temp=temp>>1;
- }
- sum+=update();
- }
- if(sum>ans)ans=sum;
- }
- void DFS(int tot,int pos)//糖果已经给了tot个人,位置指针指向pos
- {
-
- if(tot>K)return ;
- if(pos==n+1)
- {
- if(tot==K)fuck();
- return ;
- }
- else
- {
- for(int i=0;i<=K-tot;i++)
- {
- if(b[pos]+i>10.0)return ;
- add[pos]=i;
- DFS(i+tot,pos+1);
- add[pos]=0;
- }
- }
- }
- void read()
- {
- int i;
- in>>n>>K>>A;
- for(i=1;i<=n;i++)
- {
- in>>a[i]>>b[i];
- b[i]/=10.0;
- }
- }
- void work()
- {
- DFS(0,1);
- }
- int main()
- {
- //int start,end;
- //start=clock();
- read();
- work();
- print(ans,6);
- //end=clock();
- //out<<end-start<<endl;
- return 0;
- }