题意：
给N个数，求其中长度大于等于F的子段的最大平均值。
思路：
网上一些dp的方法是由长度n-1的最优值得到长度n的最优值的dp方法明显是错的，后来看了04年国家集训队周源的论文。这题采用的数形结合的方法把优化平均值转化为优化斜率，优化过程中用到了类似求凸包的技巧和单调队列，具体的可去搜下上述论文，里面有这题的详细思路。
代码：
<pre name="code" class="cpp">//by sepNINE
#include <iostream>
#include <cmath>
using namespace std;
const int maxN=100010;char ch;
int scan()
{int res;while( ch = getchar(), ch < '0' || ch > '9' ); res = ch - '0';while( ch = getchar(), ch >= '0' && ch <= '9' )res = res*10 + ch - '0';return res;
}struct node
{double x,y;
}pnt[maxN], q[maxN];
int a[maxN];int dblcmp( double x )
{if( fabs(x) < 1e-12 )return 0;return x > 0 ? 1 : -1;
}double cross( node p0, node p1, node p2)
{return (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x);
}double getk( node a , node b)
{return (b.y-a.y)/(b.x-a.x);
}
int main()
{int i,j,N,F;double ans;scanf("%d%d", &N, &F);a[0] = 0;pnt[0].x = pnt[0].y = 0;for( i = 1; i <= N; ++i ){a[i] = scan() + a[i-1];pnt[i].x = (double)i;pnt[i].y = (double)a[i]; }ans = -1.0;int r = 0, l = 1;for( i = F; i <= N; ++i ){node newP = pnt[i-F];while( r > 1 && dblcmp( cross( q[r-1], q[r], newP ) ) < 0 )--r;q[++r] = newP ;while( l < r && dblcmp( getk(q[l],pnt[i]) - getk(q[l+1],pnt[i]) ) < 0 ){++l;}ans = max( ans , getk(q[l],pnt[i]) ); }printf("%d\n" , (int)(ans*1000) );return 0;
}