CF183D T-shirt
考虑每次的选择，一定是选择一件衣服使得能送出的概率最大
f[i][j]表示，至少有j个人能穿第i个的概率
选择最大的n个f[i][j]就是答案。
直接dpO(m*n^2)会TLE
我们只要前n大，而f[i]显然单调
加入f[i][1]，选择最大的。再计算f[i][2]
O(n^2+nlogn)
#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define pb push_back #define solid const auto & #define enter cout<<endl #define pii pair<int,int> using namespace std; typedef long long ll; template<class T>il void rd(T &x){char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);} template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');} namespace Modulo{ const int mod=998244353; il int ad(int x,int y){return x+y>=mod?x+y-mod:x+y;} il int sub(int x,int y){return ad(x,mod-y);} il int mul(int x,int y){return (ll)x*y%mod;} il void inc(int &x,int y){x=ad(x,y);} il void inc2(int &x,int y){x=mul(x,y);} il int qm(int x,int y=mod-2){int ret=1;while(y){if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;} template<class ...Args>il int ad(const int a,const int b,const Args &...args) {return ad(ad(a,b),args...);} template<class ...Args>il int mul(const int a,const int b,const Args &...args) {return mul(mul(a,b),args...);} } // using namespace Modulo; #define ld long double namespace Miracle{ const int N=3003; const int M=3003; int n,m; ld f[M][N]; ld p[M][N]; int get[M]; struct po{ld val;int id;po(){}po(ld v,int d){val=v;id=d;}bool friend operator <(po a,po b){return a.val<b.val;} }; priority_queue<po>q;int main(){rd(n);rd(m);for(reg i=1;i<=n;++i){for(reg j=1;j<=m;++j){int x;rd(x);p[j][i]=(ld)x/1000;}}for(reg j=1;j<=m;++j){f[j][0]=1;for(reg i=1;i<=n;++i){f[j][i]=f[j][i-1]*(1-p[j][i]);}}for(reg j=1;j<=m;++j){ld lp=1.00;for(reg i=1;i<=n;++i) lp*=(1.00-p[j][i]);lp=1-lp; // cout<<" j "<<j<<" "<<lp<<endl; q.push(po(lp,j));}int nd=n;ld ans=0.0;while(nd--){po now=q.top();q.pop(); // cout<<" now "<<now.val<<" "<<now.id<<endl;ans+=now.val;int id=now.id;ld las=f[id][0];//get[id]?0.0:1.0;f[id][0]=0;for(reg i=1;i<=n;++i){ld tp=f[id][i]; // cout<<" tp "<<tp<<endl;f[id][i]=f[id][i-1]*(1.00-p[id][i])+las*p[id][i]; // cout<<" i "<<f[id][i]<<endl;las=tp;}f[id][0]=0;++get[id];q.push(po(now.val-f[id][n],id));} // printf("%.10Lf",ans);cout<<fixed<<setprecision(10)<<ans<<endl;return 0; }} signed main(){Miracle::main();return 0; }/*Author: *Miracle* */