看板ACMCLUB
标 题Re: [请益] 好题目q:
发信站批踢踢兔 (Fri Jul 7 20:36:34 2006)
转信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt2
1F：→ hil:To sophialiege: 「随机客」想不出来怎麽做O(1)-time update推 07/07 15:40
2F：→ hil:可以请sophialiege解释一下吗？推 07/07 15:40
结论: 抱歉想错了,如果有兴趣可以往下看
因为 dptable [i][j] 可能从 dptable[1..i-1][j-1] 来 update
而且当 dptable [i][j] 是由 dptable[u][j-1] 来 update 时
dptable[i+1][j] 就不可能是由 dptable[1..u-1][j-1] 来 update
到目前为止都对,这时想用Amortized Analysis来定time complexity是constant
这时还需要证明 dptable[1..i-1][j-1] + compensate[1..i-1][i] 是 U 形 curve
1. dptable[1..i-1][j-1] 是 non-decreasing sequence
2. compensate[1..i-1][i] 是 non-increasing sequence
由於当时天真地以为 (1) (2) 可以导出 U 形 curve的结论, so ...
--
※ 发信站: 批踢踢兔(ptt2.cc)
◆ From: 140.112.250.175