斜率优化DP。。。《浅谈数形结合思想在信息学竞赛中的应用 安徽省芜湖一中 周源》例题。。。
Best Cow Fences
| Time Limit: 1000MS |
|
Memory Limit: 30000K |
| Total Submissions: 9311 |
|
Accepted: 2986 |
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 |
[Submit] [Go Back] [Status] [Discuss]
#include
#include
#include
#include
using namespace std; const int maxn=100100; int sum[maxn],n,f; int stack[maxn],top; bool cmp(int a,int b,int c) { int x1,x2,y1,y2; y1=sum[b]-sum[a]; x1=b-a; y2=sum[c]-sum[b]; x2=c-b; return y1*x2-y2*x1<=0; } double calu(int a,int b) { return (double)(sum[b]-sum[a])/(double)(b-a); } int main() { while(scanf("%d%d",&n,&f)!=EOF) { double ans=0.; for(int i=1;i<=n;i++) { int x; scanf("%d",&x); sum[i]=sum[i-1]+x; } top=0; for(int i=0;i<=n-f;i++) { while(top>=1&&cmp(stack[top-1],stack[top],i)==false) top--; stack[++top]=i; int j=top; while(j>=1&&cmp(stack[j-1],stack[j],i+f)==false) j--; ans=max(ans,calu(stack[j],i+f)); } printf("%d\n",(int)(ans*1000)); } return 0; }