7月份主要針對于以下幾個類型:搜索,DP,圖論(部分)。
搜索:主要是DFS和BFS,特別一點是注意剪枝。
1010 Tempter of the Bone DFS+奇偶剪枝。
1016 Prime Ring Problem 簡單的DFS,第一次沒看清題目,沒注意尾部和首部相加也要是素數。可以先用一個數組把素數先標記好,那DFS就很簡單了。
1181 變形課 簡單的DFS。用鄰接矩陣將首尾字母保存,從字母‘b’開始DFS搜索。注意跳過已經搜過的字母。
1195 Open the Lock 2717 Catch That Cow 簡單BFS。注意跳過已經搜索過的。
1240 Aseroids! 簡單的BFS。錯了幾次是因為沒把數據用多維數組保存好。
1241 Oil Deposits DFS和BFS都可以。斜線方向也是可以的。
1242 Rescue BFS。但是注意可能由多個Freind,所以從Angle開始搜。
1312 Red and Black 簡單DFS。
1198 Farm Irrigation 可以用BFS,但我是用“并查集”做的。
DP:這個是弱點,所以沒做多少,只做一些簡單的。
1003 MaxSum 最長連續子序列,經典DP,基本DP。
1024 MaxSum Plus Plus 關鍵是如何降維,將O^3最后變成O^2的,否則會超時。
1114 Piggy-Bank 完全背包問題。
1159 Common Subsequence 最長公共字串,經典DP問題。
1203 I NEED A OFFER!0-1背包問題。
1257 最少攔截系統 一個簡單方法,利用vector 開一個動態數組,每次讀一個數據,從前掃描過來,遇到比所讀數據大的,就更新那個數據為所讀數據,最后,該數組長度就是導彈系統個數。
1559 最大子矩陣 對數組中的數據做下修改,對于a[i][j] 重新更新為 a[1][1]—a[i][j] 子矩陣的和,然后就可以搜一下整個數組就能得到最大子矩陣了。
1428 漫步校園 先是從終點BFS到起點,把耗費保存在一個表中,然后再從起點DFS終點求的所有路線,但注意要記錄已經遍歷過的點,下次遍歷就直接加上上次遍歷所得的路線數目,否則會超時。
圖論:主要做了 單源最短路徑--Dijkstra算法,所有點的-Floyd算法;最小生成樹--Prim算法,另外那個還沒寫過( = =! ); 最大子團--回溯法
1217 Arbitrage 建立一個有向圖,利用Floyd算法,問題也就是求通過其他點到自己有沒有增加。
1596 find the safest road 所有點最短路徑--Floyd可以解決。
1530 Maxumum Clique 最大子團 回溯法,就是耗時比較多。
1162 Eddy’s picture 最小生成樹--Prim算法
1232 暢通工程 赤裸裸的并查集。
1301 Jungle Roads 還是最小生成樹