给定一个长度为N序列，求所有长度>=F（F<=F）的子序列中，平均值最大的一个。

首先可以想到分数规划，但是不好处理那个长度限制。然后有一张O(n)的DP方法，即以元素i结尾的最优解=以元素i-1结尾的最优解+元素i或=以元素i结尾的最短序列。仔细想会发现这个方法是错误的。正确的方法，也是比较快得方法（POJ跑到了32MS，第9名），是周源的方法（参见2004年国家集训队论文），采用数形结合的方法，化为斜率，然后证明出只需维护一个下凹的曲线即可，对于每一个点，在其“检查曲线”中寻找一个切点，如果用二分找切点则复杂度是O(NlogN)，但根据该曲线的下凹特性，斜率是递增的，因此作为切线，斜率越大则切点必然越往右，因此可以优化到O(n)，问题完美的解决了！

#include<stdio.h>
#include<string.h>

int sum[110000],stack[110000],top,now,ans1,ans2;

inline bool cmp(__int64 s1,__int64 s2,__int64 s3,__int64 l1,__int64 l2,__int64 l3)
{
    if((s3-s2)*(l2-l1)<(s2-s1)*(l3-l2))
        return true;
    return false;
}

int main()
{
    int N,F,i,j,t;
    char c;

    scanf("%d%d",&N,&F);
    for(i=1,sum[0]=0;i<=N;i++)
    {
        scanf("%d",&t);
        sum[i]=sum[i-1]+t;
    }

    for(ans1=sum[F],ans2=F,now=0,top=1,i=F+1;i<=N;i++)
    {
        while(top>1&&cmp(sum[stack[top-2]],sum[stack[top-1]],sum[i-F],stack[top-2],stack[top-1],i-F))
            top--;
        stack[top++]=i-F;
        if(now>=top)
            now=top-1;
        while(now<top-1&&!cmp(sum[stack[now]],sum[stack[now+1]],sum[i],stack[now],stack[now+1],i))
            now++;
        if((__int64)(ans1)*(__int64)(i-stack[now])<(__int64)ans2*(__int64)(sum[i]-sum[stack[now]]))
            ans1=sum[i]-sum[stack[now]],ans2=i-stack[now];
    }
    printf("%dn",1000*ans1/ans2);
}