Best Cow Fences POJ - 2018 斜率dp，限制长度

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int sum[N],dp[N];
int q[N];
inline double calc(int j,int i) {
    return (double)(sum[i]-sum[j])/(i-j);
}
int main()
{
    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        sum[0]=0;
        for(int i=1;i<=n;i++)
        {
            int val;
            scanf("%d", &val);
            sum[i]=sum[i-1]+val;
        }
        double ans=0;
        int l=1,r=0;
        q[1]=0;
        for(int i=k; i<=n; i++) {
            int j=i-k;
            while(l<r && calc(q[r], q[r-1] ) >=calc(i-k,q[r-1]))
                r--;
            q[++r]=j;
            while(l<r && calc(q[l+1],i)>=calc(q[l],i))
                l++;
            ans=max(ans,1.0*(sum[i]-sum[q[l]])/(i-q[l]) );
        }
        printf("%d\n", (int)(ans*1000));
    }
 } 

Best Cow Fences POJ - 2018 斜率dp，限制长度

原文：https://www.cnblogs.com/QingyuYYYYY/p/12517060.html