http://www.cs.nctu.edu.tw/~huanpo/0519.ppt


robertanders 發表在 痞客邦 留言(0) 人氣()

講義

robertanders 發表在 痞客邦 留言(1) 人氣()

講義

http://www.cs.nctu.edu.tw/~huanpo/109.pptx

robertanders 發表在 痞客邦 留言(2) 人氣()

来看一下ST算法是怎么实现的(以最大值为例):
  首先是预处理,用一个DP解决。设a是要求区间最值的数列,f表示从第i个数起连续2^j个数 中的最大值。例如数列3 2 4 5 6 8 1 2 9 7 ,f[1,0]表示第1个数起,长度为2^0=1的最大值,其实就是3这个数。 f[1,2]=5,f[1,3]=8,f[2,0]=2,f[2,1]=4……从这里可以看出f其实就等于a。这样,Dp的状态、初值都已经有了,剩下的 就是状态转移方程。我们把f平均分成两段(因为f一定是偶数个数字),从i到i+2^(j-1)-1为一段,i+2^(j-1)到i+2^j-1为一段 (长度都为2^(j-1))。用上例说明,当i=1,j=3时就是3,2,4,5 和 6,8,1,2这两段。f就是这两段的最大值中的最大值。于是我们得到了动规方程F=max(F,F).

robertanders 發表在 痞客邦 留言(1) 人氣()

這題長的跟ACM 105幾乎一樣

當初那題是怎麼做的呢

robertanders 發表在 痞客邦 留言(0) 人氣()

架構想了好幾個 想到快崩潰了

不過最後經由學長指點

robertanders 發表在 痞客邦 留言(0) 人氣()

Bug太多 差點沒崩潰Orz

最後總算是找出錯誤點 然後AC了

robertanders 發表在 痞客邦 留言(1) 人氣()

第一題SSSP用Dijkstra with heap完成的

我想到時候可能會需要看一看Johnson's algorithm

robertanders 發表在 痞客邦 留言(0) 人氣()

可以知道 這情況下可以用一個table判重

因此估計之後就可以用搜尋求出所有解答

robertanders 發表在 痞客邦 留言(0) 人氣()

USACO Gold

因為剛好只有N-1個邊

robertanders 發表在 痞客邦 留言(0) 人氣()