Robert Anderson's Blog

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

講義
http://www.cs.nctu.edu.tw/~huanpo/1225GamingTree.ppt
程式碼 Source Code
http://www.cs.nctu.edu.tw/~huanpo/1225Demo.cpp
程式碼(優化版) Source Code with table
http://www.cs.nctu.edu.tw/~huanpo/1225DemoTable.cpp
測資 Test Data
http://www.cs.nctu.edu.tw/~huanpo/Test Data.rar

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

来看一下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）.
　　接下来是得出最值，也许你想不到计算出f有什么用处，一般毛想想计算max还是要
O(logn)，甚至O(n)。但有一个很好的办法，做到了O（1）。还是分开来。如在上例中我们要求区间[2，8]的最大值，就要把它分成[2,5]和
[5,8]两个区间，因为这两个区间的最大值我们可以直接由f[2，2]和f[5，2]得到。扩展到一般情况，就是把区间[l，r]分成两个长度为2^n
的区间（保证有f对应）。直接给出表达式：
　　k:=ln(l(r-l+1)/ln(2));
　　ans:=max(F[l，k],F[r-2^k+1,k]);
　　这样就计算了从i开始，长度为2^t次的区间和从r-2^i+1开始长度为2^t的区间的最大值（表达式比较烦琐，细节问题如加1减1需要仔细考虑

這題長的跟ACM 105幾乎一樣
當初那題是怎麼做的呢
基本上就是模擬
可是這邊L超大

架構想了好幾個 想到快崩潰了
不過最後經由學長指點
最後終於把其中一個我想過的架構的bug除掉 完成了最後版本
簡單的來說每個點都有一個in點 是給source指向的

Bug太多 差點沒崩潰Orz
最後總算是找出錯誤點 然後AC了
因為我做法是枚舉一個切斷點
我想說可以找到一個點 去作一個尋找LOWER BOUND的動作 直接跳躍前進

第一題SSSP用Dijkstra with heap完成的
我想到時候可能會需要看一看Johnson's algorithm
這題SPFA效能不足以通過需求
因為他非接近樹狀圖的話可能就沒有很快了

可以知道 這情況下可以用一個table判重
因此估計之後就可以用搜尋求出所有解答
接著用海龍公式求出該形成之三角形面積
 

USACO Gold
因為剛好只有N-1個邊
這樣是一個樹狀圖
自然可以用一個O(N)的做法去作樹狀動態規劃