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