如此唐氏一题，为何评蓝？

我们考虑一个数组 $nxt_{i,j}$ 表示以 $i$ 往后 $j$ 个的斜率最大值

然后就可以进行转移了，设 $dp_i$ 表示以 $i$ 为结束的选的点的最少个数，显然可以进行刷表法

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 5005
using namespace std;
bool Test_MLE_start;
int T=1,n,m;
int x[N],y[N],nxt[N][N],dp[N];
inline int reads(){
	char c=getchar();
	int sum=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		sum=(sum<<3)+(sum<<1)+(c^'0');
		c=getchar();
	}
	return sum*f;
}
inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
double calc(int x1,int y1,int x2,int y2){
	return 1.0*(y2-y1)/(x2-x1);
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	T=reads();
	while(T--){
		clr();
		memset(dp,0x3f,sizeof(dp));
		n=reads(),m=reads();
		for(int i=1;i<=n;i++) x[i]=i,y[i]=reads();
		for(int i=1;i<=n;i++){
			double maxn=-2000000000;
			for(int j=i+1;j<=min(n,i+m);j++){
				double p=calc(x[i],y[i],x[j],y[j]);
//				nxt[i][j]=max(nxt[i][j-1],p);
				nxt[i][j]=nxt[i][j-1];
//				cout<<i<<" "<<j<<":"<<maxn<<" "<<p<<"\n";
				if(maxn<=p){
					maxn=p;
					nxt[i][j]=j;
				}
//				cout<<i<<" "<<j<<":"<<nxt[i][j]<<"\n";
			}
		}
//		for(int i=1;i<=n;i++){
//			for(int j=1;j<=n;j++){
//				cout<<nxt[i][j]<<" ";
//			}
//			puts("");
//		}
		dp[1]=1;
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=min(n,i+m);j++){
				dp[nxt[i][j]]=min(dp[nxt[i][j]],dp[i]+1);
			}
		}
//		for(int i=1;i<=n;i++){
//			cout<<dp[i]<<" ";
//		}
//		puts("");
		printf("%lld\n",dp[n]);
	}
	return 0;
}