cataclysm【题解】【考试】

前言

是CF上一道题，被用来当做考题了

题面描述

现在砰砰博士检测到通道中有 n 个虫洞,每个虫洞无论成功与否只能传送一人,并且这个时空通道
只能进入 n 人;
每个虫洞有一个特征值,特征值在 [1, m] 之间,只有特征值和虫洞相同的人才能被成功传送;
但由于虫洞的不稳定性,每个虫洞的特征值是无法预知的,具体来说,对于第 i 个虫洞,其特征值
为 j 的概率是 p i,j ;
n 个人进入时空通道之后,虫洞的特征值就确定下来,即这 n 个人在进入时空通道之后,可以自由
选择进入何种虫洞,但是无法返回。
砰砰博士希望你找到使得被成功传送的期望人数最多的方法,这样才能最大限度地挽救这片土地上
的人民。

sol

想到一个简单的dp就是对于而枚举每一个人，然后枚举他去哪里。
我们令每一个人选的特征值必须递增，所以就用dp记一下当前特征值的最大值是什么，有几个人选了，接下来的这个人可以选择继续选也可以把这一个状态转移到下一个特征值选0个的状态去。
但是这是n^3
n^2就会发现每一个特征值的选举，第i个人选的期望如果是pi,那么$p_i>p_{i+1}$所以就可以贪心

code

#include<bits/stdc++.h>
#define LL long long
#define eps 1e-8
using namespace std;
inline char gc(){
    static char buf[1<<6],*p1=buf,*p2=buf;
    return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<6,stdin),p1==p2)?EOF:*p1++;
}
template <class T>
inline void read(T&data){
    data=0;
    register char ch=0;
    while(ch<'0'||ch>'9')ch=gc();
    while(ch<='9'&&ch>='0'){
        data=(data<<3)+(data<<1)+(ch&15);
        ch=gc();        
    }return;
}
const int _ =3001;
double p[3001][_],P[_][2][_];
int n,m;
struct data{
    double zh;
    int from,cc;
    bool operator <(const data& a)const {
        return eps<a.zh-zh;
    }
};
priority_queue<data> Q;
inline void update(register data&A ,register int ki,register int cc){
    register int pre=(cc+1)%2,cur=cc%2;
    for(register int i=0;i<=n;++i)P[ki][cur][i]=0;
    for(register int i=1;i<=n;++i)P[ki][cur][i]=P[ki][pre][i-1]*p[i][ki]+P[ki][cur][i-1]*(1-p[i][ki]);
    A.zh=A.zh-P[ki][cur][n];A.cc++;return;
}
int main(){
    freopen("cataclysm.in","r",stdin);
    freopen("cataclysm.out","w",stdout);
    read(n),read(m);
    for(register int i=1;i<=n;++i)
        for(register int j=1,h;j<=m;++j)
            read(h),p[i][j] =1.0 * h/1000.0;            
    register double ans=0;
    for(register int i=1;i<=m;++i){
        P[i][0][0]=1;
        for(register int j=1;j<=n;++j)
            P[i][0][j]=P[i][1][j-1]*p[j][i]+P[i][0][j-1]*(1-p[j][i]);       
    }
    for(register int i=1;i<=m;++i)
        Q.push((data){1-P[i][0][n],i,1});
    for(register int i=1;i<=n;++i){
        register data qio=Q.top();Q.pop();
        ans+=qio.zh;
        if(qio.cc==n)continue;
        update(qio,qio.from,qio.cc);
        Q.push(qio);
    }
    printf("%.9lf",ans);
}
/*

2 2
500 500
500 500
 */