CF601C Kleofáš and the n-thlon(期望+前缀和优化dp)

解题思路

　　要求这个人的排名，我们可以先求出某个人比他排名靠前的概率，然后再乘上\(m-1\)即为答案。求某个人比他排名靠前可以用\(dp\)，设\(f[i][j]\)表示前\(i\)场比赛某人的得分为\(j\)的概率，那么转移方程为:\(f[i][j]=\sum\limits_{k=1,k!=x[i]}^(min(m,j)) f[i-1][j-k]\)，发现这个复杂度是\(O(n^2*m^2)\)的，无法接受。进一步可以看出转移形式可以前缀和优化，只需要加上前缀和后把\(k=x[i]\)这个地方挖去即可。这样时间复杂度为\(O(n^2*m)\)的，然后用滚动数组优化空间。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

using namespace std;

const int MAXN = 105;

const int MAXM = 1005;

inline int rd(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return f?x:-x;

}

int n,m,tot,x[MAXN];

double f[2][MAXM*MAXN],ans,sum;

int main(){

    n=rd(),m=rd();f[0][0]=1.0;

    for(int i=1;i<=n;i++) x[i]=rd(),tot+=x[i];

    for(int i=1;i<=n;i++){

        sum=f[(i-1)&1][0];

        for(int j=1;j<tot;j++){

            f[i&1][j]=sum;

            if(j>=x[i]) f[i&1][j]-=f[(i-1)&1][j-x[i]];

            sum+=f[(i-1)&1][j];

            if(j>=m) sum-=f[(i-1)&1][j-m];

            f[i&1][j]/=(m-1);

        }

        if(i==1) f[0][0]=0;

    }

    for(int i=n;i<tot;i++)

        ans+=f[n&1][i];

    printf("%.15lf",ans*(m-1)+1.0);

    return 0;

}