poj 2018 斜率DP 求子序列的最大平均值

本文主要是介绍poj 2018 斜率DP 求子序列的最大平均值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<cstdio>
#include<cstring>
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)>(y)?(y):(x))
struct node
{double x,y;
}q[100100];
double cal(double x1,double y1,double x2,double y2)
{return  (y1-y2)/(x1-x2); 
}
double sum[100100]; 
int main()
{int n,f;scanf("%d%d",&n,&f);memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++){scanf("%lf",&sum[i]);sum[i]+=sum[i-1];}q[0].x=0;q[0].y=0;int head=0,tot=0; double ans=-1; for(int i=1;i<=n;i++){ while(head<=tot&&q[head].x+f<=i)head++;if(head>0) {ans=MAX(ans,(sum[i]-q[head-1].y)/(i-q[head-1].x));		  }while(head<tot&&cal(q[tot].x,q[tot].y,q[tot-1].x,q[tot-1].y)>cal(i,sum[i],q[tot].x,q[tot].y))tot--;q[++tot].x=i;q[tot].y=sum[i];} printf("%d\n",(int)(ans*1000));return 0; 
}

这篇关于poj 2018 斜率DP 求子序列的最大平均值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---