hdu 2993 斜率dp

思路：直接通过斜率优化进行求解。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#define Maxn 1000010

using namespace std;

__int64 sum[Maxn];

__int64 num[Maxn];

int que[Maxn*];

int main()

{

    int n,k,head,rear,x;

    int i,j;

    double ans;

    while(scanf("%d%d",&n,&k)!=EOF){

        ans=;

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

            scanf("%I64d",&num[i]);

            sum[i]=sum[i-]+num[i];

        }

        head=,rear=;

        que[++rear]=;

        for(i=k;i<=n;i++){

            j=i-k+;

            while(head<rear&&(sum[i]-sum[que[head+]])*(i-que[head])>=(sum[i]-sum[que[head]])*(i-que[head+]))

                head++;

            ans=max(ans,(double)((double)sum[i]-(double)sum[que[head]])/(double)((double)i-(double)que[head]));

            while(head<rear&&(sum[j]-sum[que[rear]])*(que[rear]-que[rear-])<=(sum[que[rear]]-sum[que[rear-]])*(j-que[rear]))

                rear--;

            que[++rear]=j;

        }

        printf("%.2lf\n",ans);

    }

    return ;

}