1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
|
#include<algorithm> #include<cstring> using namespace std; namespace io{ #define re register #define ll long long #define inf 0x3f3f3f3f #define il inline #define in1(a) read(a) #define in2(a,b) in1(a),in1(b) #define in3(a,b,c) in2(a,b),in1(c) #define in4(a,b,c,d) in2(a,b),in2(c,d) il void (ll &x){ x=0;ll f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} x*=f; } il void read(int &x){ x=0;int f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} x*=f; } }using namespace io; #define N 5005 int n,k; int h[N],f[N]; int main(){ in2(n,k); for(re int i=1;i<=n;i++) read(h[i]); f[1]=1; for(re int i=2;i<=n;i++){ f[i]=inf; int a=inf,b=1; for(re int j=i-1;j>=max(i-k,1);j--){ if(1ll*(h[i]-h[j])*b<=1ll*a*(i-j)) a=h[i]-h[j],b=i-j,f[i]=min(f[i],f[j]+1); } } printf("%d",f[n]); return 0; }
|
近期评论