斜率優化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.Input
* Line 1: Two space-separated integers, N and F.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; }