状态: 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;
}