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