龙贝格积分的基本思想就是先利用复化梯形公式把曲线划分若干小区间,把每个小区间当成梯形来求和;然后每次将区间数加倍,直到收敛到一定精度范围内为止。
程序基本参照计算方法的书写的,但是开始写完之后发现巨慢。找了网上一个版本和我的比较下,发现我们俩只是二维数组的两个维代表的含义互换了,但是时间复杂度完全相同。后来改了一下发现居然快很多,囧。之后可以过JOJ 2457。但是仍然过不了HOJ 2539。一旦把精度调高就TLE,郁闷。
后来找到了liuyu大牛曾经写过的romberg积分模板,发现巨快,研究了一下发现他把那个T数组巧妙的压缩成了一维,但是总时间复杂度不变,不知道为什么那么快,也许是因为二维数组遍历的时候寻址比较耗时间吧。按照他的方法改了下,仍然过不了,但是这回是WA。找了很久发现在更新的时候每次乘以定值就会WA,用pow才可以过,估计是数据的精度有问题。改了之后终于过了,速度很快:-)
posted on 2009-05-20 19:56
sdfond 阅读(956)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm - Ad Hoc