讨论 / 考分鄙视。。。我真鄙视自己。。70分。。。。
Nr 2010-03-14 10:15:00
点我顶贴 收藏 删除
通过本测试点|有效耗时172ms

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

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

测试结果4: 通过本测试点|有效耗时156ms

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

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

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

测试结果8: 选手程序运行超过时限

9和10都结果错了

估计是越界

核心是

for i:= n downto 2 do{倒过来循环}

for j:=1 to i-1 do{在i前面的j~~}

if a[i]>a[j]+(i-j) then{如果a[j]的值大于a[i]}

if f[j]<>0 then {如果f[j]里面原来有存东西}

begin

f[i]:=f[j]+1;break;{就直接加上}

end

else

f[i]:=f[i]+1;{否则算一遍}

用动态储存节约时间。

问!!!!

我看最优解是

通过本测试点|有效耗时94ms

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

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

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

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

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

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

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

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

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

怎么做的!!

几乎是时间复杂度是没多大变化的!!

求解!!

#1 chowfun@2010-03-14 10:15:00
回复 删除
回复 楼主Nr 的帖子

逆序对。

#2 chyc@2017-01-28 14:19:10
回复 删除
回复 #1 chowfun:代码

查看更多回复
提交回复