状态: Unaccepted

测评机： Virmain[1]

得分： 90分

提交日期： 2013-10-11 15:29:00

有效耗时： 907毫秒

测试结果1: 通过本测试点|有效耗时63ms

测试结果2: 通过本测试点|有效耗时62ms

测试结果3: 通过本测试点|有效耗时63ms

测试结果4: 测试结果错误.错误结果为:579

正确结果应为:581

测试结果5: 通过本测试点|有效耗时297ms

测试结果6: 通过本测试点|有效耗时47ms

测试结果7: 通过本测试点|有效耗时219ms

测试结果8: 通过本测试点|有效耗时46ms

测试结果9: 通过本测试点|有效耗时63ms

测试结果10: 通过本测试点|有效耗时47ms

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 5010

int n,k;

int fz[N],dp[N];

long long a[N];

bool pd(int i,int j,int k)

{

if ((a[i]-a[k])*(i-j) <= (a[i]-a[j])*(i-k)) return true;

return false;

}

int main()

{

scanf("%d%d",&n,&k);

for (int i=1;i<=n;i++)scanf("%d",&a[i]);

for (int i=1;i<=n;i++)

{

fz[i]=i-1;

dp[i]=dp[i-1]+1;

int M=max(1,i-k);

for (int j=i-2;j>=M;j--)

if (pd(i,fz[i],j)){

if (dp[i] > dp[j]+1)

{fz[i]=j;dp[i]=dp[j]+1;}

}

}

printf("%d\n",dp[n]);

//system("pause");

return 0;

}