[BZOJ1721][Usaco2006 Mar]Ski Lift 缆车支柱

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define int long long
 6 using namespace std;
 7 inline int read(){
 8     char chr=getchar();    int f=1,ans=0;
 9     while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
10     while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
11     return ans*f;
12 }int n,m,h[5005],dp[5005];long double k,maxn;
13 signed main(){
14     n=read(),m=read();for(int i=1;i<=n;i++)h[i]=read();
15     for(int i=1;i<=n;i++)dp[i]=9223372036854775803ll;dp[1]=1;
16     for(int i=1;i<=n;i++){
17         maxn=-2147483647;
18         for(int j=1;i+j<=n&&j<=m;j++)
19             k=(h[i+j]-h[i])*1.0/(j*1.0),(k>=maxn)?(dp[i+j]=min(dp[i+j],dp[i]+1),maxn=k):1;
20     }cout<<dp[n];
21     return 0;
22 }