测评机： Xeond[6]
得分： 60分
提交日期： 2010-8-9 13:03:00
有效耗时： 1016毫秒
测试结果1: 通过本测试点|有效耗时172ms
测试结果2: 通过本测试点|有效耗时62ms
测试结果3: 通过本测试点|有效耗时172ms
测试结果4: 通过本测试点|有效耗时172ms
测试结果5: 选手程序运行超过时限
测试结果6: 测试结果错误.错误结果为:581
正确结果应为:102
测试结果7: 测试结果错误.错误结果为:581
正确结果应为:5000
测试结果8: 测试结果错误.错误结果为:581
正确结果应为:102
测试结果9: 通过本测试点|有效耗时219ms
测试结果10: 通过本测试点|有效耗时219ms
{$inline on}
var
h,f:array[0..5000] of longint;
i,j,k,x,y,z,n:longint;
minx,jj:extended;
function max(a,b:longint):longint;
begin
if a>b then exit(a);
exit(b);
end;
function get(y,x:longint):extended; inline;
begin
exit(arctan(y/x)+pi);
end;
begin
readln(n,k);
for i:=1 to n do readln(h[i]);
for i:=1 to n do f[i]:=maxlongint;
f[1]:=0;
for i:=1 to n do
begin
minx:=maxlongint;
for j:=i-1 downto max(i-k,1) do
begin
jj:=get(h[i]-h[j],i-j);
if (jj<minx) or (abs(jj-minx)<=1e-10) then
begin
if f[i]>f[j] then
f[i]:=f[j];
minx:=jj;
end;
end;
inc(f[i]);
end;
writeln(f[n]);
end.
设f(i)是从1号支架建轨道，修到第i支架，并且要在此固定（也就是一个从1到i的子问题）所需要的最少固定点数目。对于f(i)，说明要在i固定，而之前的一个的固定点p只可能在[i-k,i-1]区间内，而且与1..p区间的具体固定方案无关，只与从1到p并在p固定所需要的最少固定点数目有关，符合动态规划的原理，可写出状态转移方程如下：
F[i] = Min(F[p]) + 1
(之前最优状态费用) （在i固定的费用）
其中p是可以使用的“上一个”固定点。
通过上述状态转移方程，不难得出一个O(n2) 的动态规划框架。但是关于如何判断两点之间是否可以连接轨道，一般做法还要消耗很多的时间，最好是可以在O(1)的时间内得出判断结果。
需要计算斜率才可以得到具体的结果，但是是否要每穷举一个状态都要算他们之间所有点的允许斜率呢？其实在每一个阶段，会有大量重复的斜率计算。如果枚举状态时“倒序” 枚举，就可以每次只计算当前点到终点的斜率，再与之前得出的“最大允许斜率”（之前出现的最小斜率）比较。如果当前的斜率较大，说明不可达；如果当前的斜率较小，说明可达，而且以后的斜率不能超过这个，更新这个“最大允许斜率”。这样，每次就是O(1)的判断了。
整个算法的时间复杂度为O(n2)。
//以上均为摘抄,仅供参考//
设f(i)是从1号支架建轨道，修到第i支架，并且要在此固定（也就是一个从1到i的子问题）所需要的最少固定点数目。对于f(i)，说明要在i固定，而之前的一个的固定点p只可能在[i-k,i-1]区间内，而且与1..p区间的具体固定方案无关，只与从1到p并在p固定所需要的最少固定点数目有关，符合动态规划的原理，可写出状态转移方程如下：
F[i] = Min(F[p]) + 1
(之前最优状态费用) （在i固定的费用）
其中p是可以使用的“上一个”固定点。
通过上述状态转移方程，不难得出一个O(n2) 的动态规划框架。但是关于如何判断两点之间是否可以连接轨道，一般做法还要消耗很多的时间，最好是可以在O(1)的时间内得出判断结果。
需要计算斜率才可以得到具体的结果，但是是否要每穷举一个状态都要算他们之间所有点的允许斜率呢？其实在每一个阶段，会有大量重复的斜率计算。如果枚举状态时“倒序” 枚举，就可以每次只计算当前点到终点的斜率，再与之前得出的“最大允许斜率”（之前出现的最小斜率）比较。如果当前的斜率较大，说明不可达；如果当前的斜率较小，说明可达，而且以后的斜率不能超过这个，更新这个“最大允许斜率”。这样，每次就是O(1)的判断了。
整个算法的时间复杂度为O(n2)。
//以上均为摘抄,仅供参考//
for i:=2 to n do
begin
min:=maxlongint；
for j:=i-1 downto max (1,i-k) do
begin
x:=(ipt[i]-ipt[j])/(i-j)；
if x<min then min:=x；
if x<=min then
if opt[j]+1<opt[i] then
opt[i]:=opt[j]+1；
end；
end；