題目
這套題之前沒有做過 不過還是沒有NOI什么也做不上的感覺
1、2、4題居然全是DP
分別是以當(dāng)前位置+路徑長度、以當(dāng)前節(jié)點(diǎn)為根結(jié)點(diǎn)的子樹+使用機(jī)器數(shù)、當(dāng)前節(jié)點(diǎn)+當(dāng)前時(shí)間為狀態(tài)
其中2題的狀態(tài)轉(zhuǎn)移又是一次DP 方法類似背包問題
第5題 我只想到了m*n*logn^2的算法：枚舉m通過二分+樹狀數(shù)組查找下一步的位置 雖然不能AC但打表還是可以的(最大的點(diǎn)用時(shí)13s)
后來在OIBH上看到了一個(gè)n^m的解法：枚舉m 將問題劃歸成長度為n-（被刪除的城市個(gè)數(shù)）北京的位置隨之改變 這樣既可以忽略被刪除的城市
特別注意m不應(yīng)定<=n
第3題 這道題總數(shù)后點(diǎn)收獲 二分圖最小點(diǎn)覆蓋問題 可惜我從來沒聽說過 現(xiàn)在聽說也不晚如果你還沒聽說過就去看看這個(gè)吧：http://www.matrix67.com/blog/archives/116
現(xiàn)在看來很簡單了 搞n+m各點(diǎn)表示每行/列 讀入01矩陣 若該點(diǎn)是1則將所在行與所在列連一條邊
剩下的工作就是求二分圖最小點(diǎn)覆蓋了 也就是它的最大匹配