龍貝格積分的基本思想就是先利用復化梯形公式把曲線劃分若干小區間,把每個小區間當成梯形來求和;然后每次將區間數加倍,直到收斂到一定精度范圍內為止。
程序基本參照計算方法的書寫的,但是開始寫完之后發現巨慢。找了網上一個版本和我的比較下,發現我們倆只是二維數組的兩個維代表的含義互換了,但是時間復雜度完全相同。后來改了一下發現居然快很多,囧。之后可以過JOJ 2457。但是仍然過不了HOJ 2539。一旦把精度調高就TLE,郁悶。
后來找到了liuyu大牛曾經寫過的romberg積分模板,發現巨快,研究了一下發現他把那個T數組巧妙的壓縮成了一維,但是總時間復雜度不變,不知道為什么那么快,也許是因為二維數組遍歷的時候尋址比較耗時間吧。按照他的方法改了下,仍然過不了,但是這回是WA。找了很久發現在更新的時候每次乘以定值就會WA,用pow才可以過,估計是數據的精度有問題。改了之后終于過了,速度很快:-)
posted on 2009-05-20 19:56
sdfond 閱讀(973)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm - Ad Hoc