自动搬运

查看原文

来自洛谷，原作者为

	AlexZhang **

搬运于2025-08-24 22:05:10，当前版本为作者最后更新于2018-10-03 18:30:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

emmm,这道题我们今天集训的一道题。。。

思路:怎么搞呢这道题，对于当前点i,我们往后枚举，求得最优值，很明显是个动态规划，但是题中很明显有着一个限制条件，就是说当i要连向j时，我们这条线不能触碰到山顶，我们设两点间连线斜率为k，那么k[i][j]要保证任何大于i小于j的一个l都要满足k[i][l]<=k[i][j],那么我们再记录一下当前点连出去的最大斜率是多少就行了，剩下的只是dp了，如果上面的不理解那么就看我代码吧

对于斜率的概念如果不懂，可以自行百度

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int f[5005],n,ki,h[5005];
int main(){
	memset(f,0x3f,sizeof(f));//既然是找最少那么我们将答案数组初始化为一个极大值
	scanf("%d%d",&n,&ki);
	for(int i=1;i<=n;i++)
		scanf("%d",&h[i]);
	f[1]=1;//起点必须得建
	for(int i=1;i<=n;i++){
		double x=-2147483647;//x最大斜率
		for(int j=1;j<=ki&&i+j<=n;j++)
			if((h[i+j]-h[i])*1.0/(j)>=x){//如果斜率大于最大斜率，那么肯定会撞上些什么
				f[i+j]=min(f[i+j],f[i]+1);//dp过程
				x=(h[i+j]-h[i])*1.0/(j);
			}
	}
	printf("%d",f[n]);//输出答案
	return 0;
}

最后祝大家NOIP顺利