Introduction to Competitive Programming
2/16
問題敘述 : 第 \(i\) 個賭局可以贏得 \(a_i\) 塊錢,以正數與負數表示表示贏錢與輸錢
選任意一局開始,連續的賭局當中最多可以贏得多少錢
題目的意思等價於求一個序列中子區間的最大連續和
分析每個 \(a_i\) 會發現只有兩種情況,一種是包含在答案的子序列中(必須是連續的),另一種是它是新的連續子序列的開頭。
而其中不包含在答案的子序列中就不必討論,只討論包含在答案的子序列中。
可以把 \(dp[i][j]\) 定義成表示第 \(i\) 項在兩種情況當中前 \(i\) 項的最大連續和
其中 \(j\) 代表前頁的第幾種情況
若 \(j=0\) 代表第 \(i\) 項包含在答案的子序列中
若 \(j=1\) 代表第 \(i\) 項是新的連續子序列的開頭
則可以求出轉移式
\[
\begin{cases}
dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + a[i] \\
dp[i][1] = a[i]
\end{cases}
\]
初始化
\[ \begin{cases} dp[0][0] = 0 \\ dp[0][1] = a[0] \end{cases} \]
為何是
\[
\begin{cases}
dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + a[i] \\
dp[i][1] = a[i]
\end{cases}
\]
因為對於 \(dp[i][0]\)(這一項必取) 來說,它包含前幾項的最好,所以它會是 \(dp[i-1][0]\)(前一項也取) 或者是 \(dp[i-1][1]\)(前一項是第一項) 的 \(max\) 加上他自己
而對於 \(dp[i][1]\) 來說,他自己就是第一項,因此它的值 (對第 \(i\) 項來說 \(i\) 就是第一個) 會是 \(a[i] + 0\)
在那之前要先補充二分搜的 \(LIS\) 作法
從 \(1\) 到 \(n\) 遍歷 \(A\) 的每個元素,每次與 \(X\)(當前LIS) 裡的元素進行檢查,
若是比結尾元素大就加入,若沒有就使用 \(lower\_bound\) 取代原本的位置。
從 \(1\) 到 \(n\) 遍歷 \(A\) 的每個元素,每次與當前 LIS 裡的元素進行檢查,
若是比結尾元素大就加入,若沒有就使用 \(lower\_bound\) 取代原本的位置。
vector<int> getLIS(vector<int> a){ vector<int> lis; for(int i : a){ if(lis.empty() || lis.back() < i) lis.push_Back(i); else *lower_bound(lis.begin(), lis.end(), i) = i; } return lis; }
為何需要轉換?
怎麼轉換?
LIS 轉 LCS :令原序列 A 排序後變成 B 。 A 和 B 的 LCS ,就是 A 的 LIS 。
LCS 轉 LIS :將序列 A 和 B 當中的相同字母配對通通找出來,表示成位置數對,以特殊規則(Counting sort)排序,然後找到 LIS ,就是 A 和 B 的 LCS 。
LCS 轉 LIS 於是你會發現二維平面的 LCS 會變成二維平面的 LIS
二維平面的 LIS 聽起來複雜度並沒有比較好,因此
所有數對:第一維由小到大排序;當第一維平手,則第二維由大到小排序。
排序之後,原本數對們的 2D LIS =第二維的 1D LIS
於是就可以將LCS在經過一連串的預處理之後變成 \(O(n \log n )\) 的時間複雜度。
ex :
\(string_1\) : horse
\(string_2\) : ros
所謂 Edit distance 就是 \(string_1\) 最少要幾步才能變成 \(string_2\) ,而其中每一步可以是 “新增”、“刪除” 或是 “取代”。所以第一個範例 horse 經過了
就可以得到 ros ,共花了 3 步 (3 就是答案)。
通常如果是需要去比對兩個字串的題目,我們會定義狀態為一個二維陣列 \(dp[i][j]\)
\(dp[i][j]\) 為 \(string_1\) 中前 \(i\) 個字元的字串和 \(string_2\) 中前 \(j\) 個字元的字串的 Edit Distance
而我們知道子問題後,我們的答案就顯而易見是 \(dp[len(string_1)][len(string_2)]\)
而很重要的初始化會發現,每個字串到空字串之間最快的路徑就是直接"消除",因此會有以下初始化 :
\[
\begin{cases}
dp[i][0] = i \ , i \leq len(string_1)\\
dp[0][j] = j \ , j \leq len(string_2)\\
\end{cases}
\]
然後我們只需要思考, \(dp[i][j]\) 可以怎麼轉移。
分別有兩點
所以可以總結出狀態轉移方程為 \(dp[i][j]= min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])+1\)
\(\texttt{時間複雜度}\) | \(\texttt{空間複雜度}\) | \(\texttt{狀態轉移式}\) | |
---|---|---|---|
LIS | \(n\log n\) | \(n\) | \(\texttt{max(dp[i],dp[j]+1)}\) |
LCS | \(n^2\) | \(length(str_1)\) | \(\texttt{dp[i-1][j-1]+1}\) or \(\texttt{max(dp[i][j-1], dp[i-1][j])}\) |
Edit distance | \(n^2\) | \(length(str_1)\) | \(\texttt{min(dp[i][j-1]},\\ \texttt{dp[i-1][j]},\\ \texttt{dp[i-1][j-1])+1}\) |
給一個陣列
ex : {3, 34, 4, 12, 5, 2}, sum = 9
如果裡面的數字挑選幾個出來,相加等於 9
就代表符合這個問題。
首先會思考到,由於只能挑跟不挑,所以可以暴力枚舉每一個數字是否再答案裡面,然後再思考一下時間複雜度就會發現,需要的量級是指數級的,為 \(O(2^n)\) 所以 \(n\) 稍微大一點就很容易TLE
所以會需要使用到動態規劃,令 \(dp[i][j]\) 表示 \(arr\) 中前 \(i\) 個元素的子集和等於 \(j\) 的情況,則
若 \(arr[i] > j\) ,則 \(arr[i]\) 不在子集 \(subset\) 中。
若 \(arr[i] \le j\) , 則有以下兩種情況:一種情況是 \(arr[i]\) 不在子集 \(subset\) 中,則 \(dp(i, j) = dp(i-1, j)\) 一種情況是 \(arr[i]\) 在子集 \(subset\) 中,則 \(dp[i][j]= dp[i-1][j-arr[i]]\)
這樣就有了這個問題的子結構問題,因此,只需要確定初始情況即可
而初始情況即為對於 \(i=0,1,2,...,n\) ,有 \(dp[i][0]=True\) , 對於 \(j=1,2,...,M\) , 有 \(dp[0][j]=False\)
然後你就會發現代碼會長這樣
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(j<arr[i])
dp[i][j] = dp[i-1][j]
else
dp[i][j] = dp[i-1][j] | dp[i-1][j-S[i-1]]
而倘若你需要知道 subset 是由那些 sub_element 組合成的,則可以把 DP 的真值表印出來,參考上次 LCS 的回朔法使用查詢。
例題 : zerojudge a416
題目敘述轉化 : 把一列大小為 \(n\) 整數序列分成兩個子集且讓兩個子集的 sum 最接近
那這邊我們就可以用到 bitset 的思想,首先先介紹一下 bitset 的用法和為何使用 bitset :
對於這道題,我們用 bitset 來替代 DP,bits[j] 的含義與 DP[j] 的含義相同。就是是否有這樣的一個子集的總和是 \(j\)
假設現在有一個數組 {2,3,5,2,3,5} 很明顯可以看出它的解答是 \(2+3+5=10\) 那對於我們的 bitset 數組會長這樣
bitset<N> dp(1);
dp {1} //代表0可以選 (有一個子集合是0)
dp {101} //加入'2' 了,把原本所有1的bit左移兩個 現在代表 '2' 和 '0' 都可以有子集合
dp {101101} //加入'3'了,把原本所有1的bit左移三個 '0' '2' '3' '5' 都有子集合
dp {10110101101} //加入'5'了,把原本所有1的bit左移五個
//依此類推
到最後只要詢問 \(sum/2\) 開始往左右邊遍歷就可以知道答案了。
滾動數組的作用在於優化空間。因為DP題目是一個自底向上的擴展過程,我們常常需要用到的是線性的解,前面的解往往不用紀錄。所以用滾動數組優化是很有效的。利用滾動數組的話在N很大的情況下可以達到壓縮存儲的作用,通常可以直接壓掉一個維度的大小。
ex: dp[N][M] \(\to\) dp[N]
int cur,pre=1,ppre=0;
for(int i=2;i<=n;i++)
cur=pre+ppre,ppre=pre,pre=cur;
一個\(n\times n\)方格棋盤,從左上角走到右下角,每次只能往右走一格或者往下走一格。請問有幾種走法?
example :
第一步 分割問題 會發現對於任何一個方格來說,只可能「從上走來」或者「從左走來」,答案是兩者相加,也就是說可以從上方以及左方的方格步數推算出當前這格的步數。
設計轉移式 \(dp[i][j]\)代表走到當前 \(i\), \(j\) 格有幾種方法,因此\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\)
然後這時候就會發現,他的轉移式只需要用到\(i\)的前一項或者是\(j\)的前一項,那是否可以節省空間呢
答案是必然的,如果不需要儲存所有問題的答案,只想要得到其中一個特定問題的答案,那只需要一維陣列就夠了,也就是 O(N) 空間。
for (int i=1; i<N; i++)
for (int j=1; j<N; j++)
f[j] += f[j-1];
就成功的作出了空間優化了
關於最大連續子區間和
同時會發現到dp轉移式裡面只轉移 \(i\) 以及 \(i-1\) ,這可以使用 rolling 壓縮空間複雜度,因此會變成這樣。
dp[i&1][0] = max(dp[(i-1)&1][0], dp[(i-1)&1][1]) + m;
dp[i&1][1] = m;
而時間複雜度會是\(O(n)\)