因為獨立插頭還有最小表示法沒有打過，獨立插頭沒看懂，廣義路徑連看都沒看過，所以這些不再本文的總結範圍內。
去年學插頭dp的時候還是很懼怕的，也只做了一題，還是按著課件對著標程打的。還好今年終於懂得原理了。其實打多了也變成模板了（當然每題的轉移不一樣）。
插頭dp有下面的分類：
按模型：多迴路問題、單迴路問題、簡單路徑問題、廣義路徑問題
按表示方法：是否有插頭、括號法（廣義括號法）、最小表示法
插頭dp最樸素的實現就是用f[i][j][k]記下在(i, j)這個點輪廓線狀態為k的答案。空間上很大，所以一般用佇列實現了。而且佇列實現可以免去動規陣列初始化的麻煩。
佇列實現需要乙個hash，對於記憶體比較寬裕的題目，可以直接開乙個桶解決。
參考資料
基於連通性狀態壓縮的動態規劃問題 - 陳丹琦
多迴路問題
這類問題是最水的，只要記錄當前位置有沒有插頭即可。比如說hdu1693。
有上插頭和左插頭 → 沒有右插頭或下插頭
沒有上插頭或做插頭 → 有右插頭和下插頭
只有乙個插頭 → 右插頭和下插頭分別只有乙個
單迴路問題
這類問題得維護連通性使得只存在乙個聯通快。具體的做法課件上講的很清楚。例題有：
ural1519 formula 1
poj1739 （如果在外面加一圈障礙的話，就變成上面那題了）
bzoj1187 （這題允許任意起點，並且不要求遍歷全圖）
限制起點終點的簡單路徑問題
簡單路徑問題按理來說應該用獨立插頭來解決，但是這類問題因為限制了起點和終點，所以比較好解決，只要對每個格仔的型別進行判斷，根據不同的格仔進行不同的轉移即可。比如說：
poj3133 （這題網上都說是獨立插頭，但是直接特判格仔就可以過掉了）
poj1739 （這題如果不加一圈的話，用特判的方法還是很好寫的）
DP演算法總結
1.資源問題1 機器分配問題 f i,j max f i 1,k w i,j k 2.資源問題2 01揹包問題 f i,j max f i 1,j v i w i f i 1,j 3.線性動態規劃1 樸素最長非降子串行 f i max 4.剖分問題1 石子合併 f i,j min f i,k f k...
怎樣保證插頭插座
怎樣保證插頭插座 轉換器的使用安全 插頭插座 轉換器質量不好是引發電氣火災的乙個重要起因。小小插頭插座 轉換器的質量問題將對廣大消費者的人身和財產安全構成嚴重的危害。因此，消費者在選購插頭插座 轉換器 開關時，應著重考慮產品的安全性，而影響其安全的主要有以下效能指標 標誌標誌是指示人們正確安裝 使用...
DP接頭終端電阻介紹
終端電阻和偏置電阻 乙個正規的rs 485網路 比如mpi，dp 應使用終端電阻和偏置電阻。在網路連線線非常短 臨時或實驗室測試時也可以不使用終端和偏置電阻。終端電阻 型網路兩端 相距最遠的兩個通訊埠上 併聯在一對通訊線上的電阻。根據傳輸線理論，終端電阻可以吸收網路上的反射波，有效地增強訊號強度。兩...