POJ-2018 Best Cow Fences(듀얼 플러스 DP)

Best Cow Fences Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 10174 Accepted: 3294 Description
Farmer John’s farm consists of a long row of N (1 <= N <= 100,000)fields. Each field contains a certain number of cows, 1 <= ncows <= 2000.
FJ wants to build a fence around a contiguous group of these fields in order to maximize the average number of cows per field within that block. The block must contain at least F (1 <= F <= N) fields, where F given as input.
Calculate the fence placement that maximizes the average, given the constraint. Input

Line 1: Two space-separated integers, N and F.

Lines 2..N+1: Each line contains a single integer, the number of cows in a field. Line 2 gives the number of cows in field 1,line 3 gives the number in field 2, and so on. Output

Line 1: A single integer that is 1000 times the maximal average.Do not perform rounding, just print the integer that is 1000*ncows/nfields. Sample Input

10 6 6 4 2 10 3 8 5 9 4 1 Sample Output
6500
이분가DP의 제목 앞에도 한 문제를 풀었다.시퀀스의 최대값과 최소값, 평균값이 둘 사이에 있는 것을 선택합니다.그리고 2점.이 값이 답안보다 큰지 작은지 판단하려면 dp를 사용해야 한다.수열의 모든 값을 이 평균치에서 빼면 구간이 0보다 크면 이 수열의 평균이 이보다 더 큰 것이 존재한다는 것을 의미한다.dp의 사상으로 이 서열의 최대 구간과 구간의 길이가 f보다 큰 경우를 구한다.

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>

using namespace std;
#define MAX 100000
double a[MAX+5];
double s[MAX+5];
int n,f;
int fun(double ave)
{

     double num1=s[f-1]-(f-1)*ave;
    for(int i=f;i<=n;i++)
    {
        double num2=s[i]-s[i-f]-f*ave;
        num1=num1+a[i]-ave;
        num1=max(num1,num2);
        if(num1>-1e-6)
            return 1;
    }
    return 0;
}
int main()
{
    double l,r;
    while(scanf("%d%d",&n,&f)!=EOF)
    {
        l=2000;
        r=-1;

        memset(s,0,sizeof(s));

        for(int i=1;i<=n;i++)
        {
            scanf("%lf",&a[i]);
            s[i]=s[i-1]+a[i];
            r=max(r,a[i]);
            l=min(l,a[i]);
        }
        double mid;
        while(r-l>=1e-6)
        {
             mid=(l+r)/2;
            if(fun(mid))
            {
                l=mid;
            }
            else
                r=mid;
        }
        printf("%d
",(int)(r*1000));
    }
    return 0;
}