LCP 61. 氣溫變化趨勢(shì)

【模擬】判斷大小關(guān)系一樣與否。

LCP 62. 交通樞紐

【模擬】找入度 = len(node) - 1且出度 = 0的點(diǎn)。

LCP 63. 彈珠游戲

【枚舉】由于路徑是唯一的，一個(gè)入口只會(huì)對(duì)應(yīng)一個(gè)唯一的出口；一個(gè)出口+進(jìn)入出口的方向，可以找到唯一的入口。因此，從不同入口出發(fā)的彈珠，走過(guò)的路徑在同一個(gè)格子上是不會(huì)重疊的（方向相反不算重疊），且路徑不存在環(huán)（可以畫(huà)圖理解）。枚舉所有入口，模擬即可。不需要DFS，寫(xiě)個(gè)循環(huán)就行?？傆?jì)算量m×n×4 至多4×10^6。

LCP 64. 二叉樹(shù)燈飾

【樹(shù)形DP】定義狀態(tài)（當(dāng)前節(jié)點(diǎn)，祖先節(jié)點(diǎn)開(kāi)關(guān)2的切換次數(shù)的奇偶性，父節(jié)點(diǎn)是否切換了開(kāi)關(guān)3），每個(gè)狀態(tài)表示從當(dāng)前狀態(tài)出發(fā)，最少需要操作多少次開(kāi)關(guān)，可以關(guān)閉子樹(shù)所有節(jié)點(diǎn)的燈。跑一個(gè)樹(shù)形DP。如果當(dāng)前受到祖先節(jié)點(diǎn)的開(kāi)關(guān)影響后，變成開(kāi)燈狀態(tài)，那么可以操作一個(gè)或三個(gè)開(kāi)關(guān)：操作開(kāi)關(guān)1；·操作開(kāi)關(guān)2：。操作開(kāi)關(guān)3；操作開(kāi)關(guān)123；這四種操作取最小值。如果變成關(guān)燈狀態(tài)，那么可以操作零個(gè)或兩個(gè)開(kāi)關(guān)；不操作任何一個(gè)開(kāi)關(guān)：操作開(kāi)關(guān)12；·操作開(kāi)關(guān)13；·操作開(kāi)關(guān)23：這四種操作取最小值。

LCP 65. 舒適的濕度

【DP】1.畫(huà)折線圖，問(wèn)題轉(zhuǎn)換成最小化折線圖中最大值與最小值的差。2.定義f[i] [j]表示考慮operate的前i個(gè)數(shù)，其中某些數(shù)字變成負(fù)數(shù)后，折線圖最右端點(diǎn)到折線圖最下端點(diǎn)的縱坐標(biāo)距離為時(shí)，折線圖中最大值與最小值的差的最小值（請(qǐng)注意：狀態(tài)定義中的不是坐標(biāo)，是到下界的相對(duì)距離）。3.設(shè)x=operate[i]。分類討論：取正號(hào)，折線圖往上走：f[i+x=max(f[i-1] [j]，j+x)。取負(fù)號(hào)，折線圖往下走，且縱坐標(biāo)設(shè)有小于最下端點(diǎn)的縱坐標(biāo)：f[i] [j - x]=f[i-1] [j]。取負(fù)號(hào)，折線圖往下走，且縱坐標(biāo)小于最下端點(diǎn)的縱坐標(biāo)，那么產(chǎn)生了一個(gè)新的最下端點(diǎn)，按照定義：f[i] [0]=f[i-1] [j]-j+x。