\[兔子,兔子,兔子 \]
首先,我们考虑一只兔子可以达到的最大值 \(mx_i\) 和最小值 \(mn_i\),这个可以很方便的求出来。并且每只兔子的取值是独立的。
然后,如果一个组合能被选中,那么在这个组合内部所有的兔子都取 \(mx_i\),其他的兔子都取 \(mn_i\) 的时候一定也能被选中。我们就钦定所有选的组合都是这种情况。
接下来,我们枚举这个组合内排名最低的兔子,然后把剩下的兔子分成三类,一定比它大的,既可以比它大也可以比它小的,一定比它小的。
第三类就完全不用考虑了,然后枚举在第一类种选多少,在第二类中选多少。选的个数要满足第二类选的个数加上第一类的总个数不超过 \(qualified-1\),否则当前兔子就选不了了。
预处理组合数,乘起来即可。
class RabbitProgramming{
public:
ll C[55][55],mx[55],mn[55];
void init(){
rep(i,0,50){
C[i][0]=1;
rep(j,1,i){
C[i][j]=C[i-1][j]+C[i-1][j-1];
}
}
}
ll getTeams(vt<int>points,vt<string>standings,int qualified,int selected){
init();
int n=points.size(),m=standings.size();
rd(i,m)rd(j,n)if(standings[i][j]=='Y'){
if(points[j]>0)mn[i]+=points[j],mx[i]+=points[j];
else mx[i]-=points[j];
}
ll ans=0;
rd(i,m){
int a=0,b=0;
rd(j,m)if(i!=j){
if(mn[j]>mx[i]||(mn[j]==mx[i]&&j<i))a++;
else if(mx[j]>mx[i]||(mx[j]==mx[i]&&j<i))b++;
}
rep(x,0,a){
int y=selected-x-1;
if(y<0)continue;
if(y+a>=qualified)continue;
if(y>b)continue;
ans+=C[a][x]*C[b][y];
}
}return ans;
}
};
//Crayan_r
标签:55,mn,兔子,mx,rd,points,10880,Topcoder,Problemming
From: https://www.cnblogs.com/jucason-xu/p/17323953.html