给你N个数，让你求一个连续数串的平均值最大，连续数串的个数不得低于F个

本文主要是介绍给你N个数，让你求一个连续数串的平均值最大，连续数串的个数不得低于F个，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=2018

题意很简单，就是给你N个数，让你求一个连续数串的平均值最大，连续数串的个数不得低于F个。

那么就设dp[i],为以第i个数为最后一个数所能得到的最大平均值。那么dp[i]要在两种情形中选择最大值，第一种是基于dp[i-1],把第I个数作为前面串的末尾，第二种情况自己单独起一长度为F的串。

代码如下：

#include<iostream>
using namespace std;
const int NUM = 100001;
int    cows[NUM];
int cowsum[NUM];//记录前F项之和，输入顺便打表，方便之后运算
struct DPNode{int sum;double ave;int num;
}dp[NUM];
int main(){int N,F;scanf("%d%d",&N,&F);for(int i=1;i<=N;i++){scanf("%d",&cows[i]);cowsum[i]=(i==1)?cows[i]:cowsum[i-1]+cows[i];if(i>F)cowsum[i]-=cows[i-F];}//初始换第一组数据
    dp[F].num = F;dp[F].sum = cowsum[F];dp[F].ave = (double)dp[F].sum/dp[F].num;double max = dp[F].ave;for(int i=F+1;i<=N;i++){double ave1 = (double)cowsum[i]/F;double ave2 = (double)(dp[i-1].sum+cows[i])/(dp[i-1].num+1);if(ave1>ave2){dp[i].num = F;dp[i].sum = cowsum[i];dp[i].ave = ave1;}else {dp[i].num = dp[i-1].num+1;dp[i].sum = dp[i-1].sum+cows[i];dp[i].ave = ave2;}if(dp[i].ave>max)max = dp[i].ave;}cout<<(int)(max*1000)<<endl;/*for(int i=1;i<=N;i++)cout<<i<<" "<<cows[i]<<" "<<cowsum[i]<<endl;*/return 0;
}