摘要: 既然已經說到了最長公共子序列，就把這個遞增子序列也說了。同樣的，這里subsequence表明了這樣的子序列不要求是連續的。比如說有子序列{1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }這樣一個字符串的的最長遞增子序列就是{1,3,4,5,6,7}或者{1,3,4,5,6,19}。

其實這個問題和前面的最長公共子序列問題還是有一定的關聯的。假設我們的初始的序列S1。那我們從小到大先排序一下。得到了S1'。這樣我們再球S1和S1'的最長公共子序列就可以知道答案了：）是不是有點巧妙啊。這個過程還是比較直觀的。但是這個不是這次要說的重點，這個問題有比較傳統的做法的.

我們定義L(j)是一個優化的子結構,也就是最長遞增子序列.那么L(j)和L(1..j-1)的關系可以描述成

  閱讀全文

     摘要: 在做ACM題時，經常都會遇到一些比較大的整數。而常用的內置整數類型常常顯得太小了：其中long 和 int 范圍是[-2^31,2^31)，即-2147483648~2147483647。而unsigned范圍是[0,2^32)，即0~4294967295。也就是說，常規的32位整數只能夠處理40億以下的數。
　　那遇到比40億要大的數怎么辦呢？這時就要用到C++的64位擴展了。不同的編譯器對64位整數的擴展有所不同。基于ACM的需要，下面僅介紹VC6.0與g++編譯器的擴展。
　　VCVC6.0的64位整數分別叫做__int64與unsigned __int64，其范圍分別是[-2^63, 2^63)與[0,2^64)，即-9223372036854775808~9223372036854775807與0~18446744073709551615(約1800億億)。對64位整數的運算與32位整數基本相同，都支持四則運算與位運算等。  閱讀全文