CodeForces 674C Levels and Regions

#include<bits/stdc++.h>

using namespace std;

const int maxn=2e5+5;

int N,K,head,tair;

int q[maxn];

double S[maxn],A[maxn],B[maxn],dp[maxn][55];

double calc(int i,int j,int k){return dp[k][j-1]+A[i]-A[k]-S[k]*(B[i]-B[k]);}

double x(int k){return S[k];}

double y(int k,int j){return dp[k][j-1]-A[k]+S[k]*B[k];}

bool judge(int a,int b,int c,int j){return (x(a)-x(c))*(y(a,j)-y(b,j))>=(y(a,j)-y(c,j))*(x(a)-x(b));}

int main()

{

    while(~scanf("%d%d",&N,&K))

    {

        S[0]=A[0]=B[0]=0;

        for(int i=1;i<=N;++i)

        {

            double t;scanf("%lf",&t);

            S[i]=S[i-1]+t;

            B[i]=B[i-1]+1/t;

            A[i]=A[i-1]+S[i]/t;

        }

        //printf("start\n");

        for(int i=1;i<=N;++i)dp[i][1]=A[i];

        for(int j=2;j<=K;++j)

        {

            q[head=tair=1]=j-1;

            for(int i=j;i<=N;++i)

            {

                while(head<tair&&calc(i,j,q[head])>=calc(i,j,q[head+1]))head++;

                dp[i][j]=calc(i,j,q[head]);

                while(head<tair&&judge(q[tair-1],q[tair],i,j))tair--;

                q[++tair]=i;

            }

        }

        printf("%.6f\n",dp[N][K]);

    }

}
巴特西

CodeForces 674C Levels and Regions

最新文章

热门文章
