zoj 2709 Lottery 组合数，概率，贪心 (8-F)

题目地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2709

题解：  1   组合数的计算，用DP，速度又快又简洁。

               2  首先用一个map统计出现了那些字母，以及对应的次数，然后n-总次数得到还有多少个字母可以分配，按照题意，只能是已经出现的字母。

                    想到Robbers那一题，感觉分给已经出现次数最多的比较好，或者像那题一样尽量按照比例分配，但是最后试了一下案例，探索发现案例的结果是在 28,：11：11：                    5：5的时候取到。

                  和按比例分很接近，但是49按比例分出44后，剩下的5不知按什么想啊分出3:1:1 

               3  然后YY了一下贪心，维护一个优先权队列，按每次增加一个给这个概率增加的比例选择，每次选择了以后就更新一下队列里这个struct  这个struct由在中奖字符串中                       出现的次数a，非配给这个字符的b，还有比例r =（b+1）/(b-a+1);     

               最后ac了，但是道理没想得很清楚

#include<queue>
#include<iostream>
#include<map>
#include<string>
#include<algorithm>
using namespace std;typedef long long inta;struct    rate
{int id;int a;int b;double  r;bool operator<(const  rate & b)  const{return r<b.r;}
};
inta gcd(inta a,inta b)
{if(b==0)  return a;else return gcd(b,a%b);}//int ratecmp(rate x,rate y)
//{
//   if(x.r>y.r)  return 1;
//   else return 0;
//}int main()
{int  n;inta  c[65][65];for(int i=0;i<65;i++){c[i][0]=1;c[i][i]=1;}for(int i=1;i<65;i++)for(int j=1;j<i;j++){c[i][j]=c[i-1][j]+c[i-1][j-1];}while(cin>>n){map<char,int>   themap;string win;cin>>win;int m=win.length();int all=n-m;for(int i=0;i<m;i++)themap[win[i]]++;int size=themap.size();int  *p=new int [size];map<char,int> ::iterator it;int count=0;for(it=themap.begin();count<size;count++,it++){p[count]=it->second;}sort(p,p+size);
//       for(int i=0;i<count;i++)
//        cout<<p[i]<<endl;priority_queue<rate>   pq;for(int i=0;i<size;i++){rate temp;temp.a=p[i];temp.b=p[i];temp.id=i;temp.r=p[i]+1;pq.push(temp);}for(int i=0;i<all;i++)     // 将余下的分配完{rate ra=pq.top();pq.pop();ra.b++;ra.r=ra.b+1;ra.r/=(ra.b-ra.a+1);pq.push(ra);}inta up=1;while(pq.size()!=0){up*=c[pq.top().b][pq.top().a];pq.pop();}inta down=c[n][m];inta thegcd=gcd(up,down);up/=thegcd;down/=thegcd;cout<<up<<"/"<<down<<endl;inta up1=1;up1=c[p[0]+all][p[0]];inta down1=c[n][m];inta thegcd1=gcd(up1,down1);up1/=thegcd1;down1/=thegcd1;cout<<up1<<"/"<<down1<<endl;cout<<endl;}
}