Poj 2018 Best Cow Fences(分数规划+DP&&斜率优化)

    xiaoxiao2021-03-25  25

    Best Cow Fences Time Limit: 1000MS Memory Limit: 30000K 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 Source USACO 2003 March Green

    /* 01分数规划思想+DP做法. 求长度不小于k连续一段的最大平均值. ans=(sum[j]-sum[i-1])/(j-i+1) [j-i+1>=k] 这样的话我们二分一个ans,然后让每个数都减去ans. 最后DP检验最大的连续和是否大于0即可. 复杂度O(nlogn). */ #include<iostream> #include<cstdio> #define MAXN 100001 #define eps 1e-6 using namespace std; double ans,s[MAXN],sum[MAXN],max1,min1=1e9; int n,k; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f; } bool check(double x) { double tot,m=0; for(int i=1;i<=n;i++) sum[i]=sum[i-1]+s[i]-x; for(int i=k;i<=n;i++) { tot=sum[i]-m; if(tot>=0) return true; m=min(m,sum[i-k+1]); } return false; } void erfen(double l,double r) { double mid; while(l+eps<=r) { mid=(l+r)/2; if(check(mid)) ans=mid,l=mid; else r=mid; } int x=r*1000; printf("%d\n",x); return ; } int main() { int x; while(~scanf("%d %d",&n,&k)) { max1=0,min1=1e9; for(int i=1;i<=n;i++) { s[i]=read(); sum[i]=sum[i-1]+s[i]; max1=max(max1,s[i]),min1=min(min1,s[i]); } erfen(min1,max1); } return 0; } /* 斜率优化题. 通过此题大概知道了斜率优化是什么. 因为ans=(sum[j]-sum[i-1])/(j-i+1) [j-i+1>=k]. 所以我们可以将看做二维平面中的两个点(i-1,sum[i])和(j,sum[j]). ans即为两点之间的斜率. 我们要让ans最大化. n^2的暴力可以看做是有一个点t,和点集Gt{x,0<=x<=t-k}, 扫描G中的每个点,使斜率最大化. 但是有些点对于决策是没有影响的. 现在有一个定理: 存在三个有序点i,j,k,如果满足k(i,j)>k(k,j) 即j点是直线ik上方的点,那它不会对决策产生影响. 证明的话见2004周源国家集训队论文,讲的很清楚. 这样的话我们维护一个下凸折线就好了. 我们每次都加入位置为i-k的点,维护下凸性. 如果某一点j(0<=j<=i-k)与点i的斜率最大, 则这个点显然一定是下凸折线的切点. 则它之前的点连线斜率较小也不会对决策产生影响 删掉就可以了. 这样的话由于每个点只入队出队一次 所以复杂度是O(n)的. 参考资料 2004周源国家集训队论文. */ #include<iostream> #include<cstdio> #define MAXN 100001 using namespace std; double ans,sum[MAXN],max1,min1=1e9; int n,k; struct data{double x,y;}q[MAXN]; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f; } double check(data a,data b,data c) { return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); } double Get(data a,data b) { return (b.y-a.y)/(b.x-a.x); } void slove() { data x,now;ans=0; int head=0,tail=0; for(int i=k;i<=n;i++) { x.x=i-k,x.y=sum[i-k]; while(tail-head>=2&&check(q[tail-2],q[tail-1],x)<0) tail--;//维护下凸性. q[tail++]=x; now.x=i,now.y=sum[i]; double k=Get(q[head],now); while(tail-head>0&&Get(q[head+1],now)>k)//删除没用的点. { k=Get(q[head+1],now); head++; } ans=max(ans,k); } ans*=1000; int a=ans; printf("%d\n",a); } int main() { int x; while(~scanf("%d %d",&n,&k)) { for(int i=1;i<=n;i++) x=read(),sum[i]=sum[i-1]+x; slove(); } return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-50031.html

    最新回复(0)