本文从WordPress迁移而来, 查看全部WordPress迁移文章
总结一下我做过的树型DP题目,没有固定的分析和模板,因为DP也可能搞出模板了,所以直接将题目归类,以具体题目来分析
树上求最长链
- hdu 4514 湫湫系列故事——设计风景线
- hdu 4679 Terrorist’s destroy
- sgu 149 Computer Network
- hdu 4607 Park Visit
- hdu 4612 Warm up
树dp + 背包
树dp+背包是最常见的一种模型,而且也是相对较难的,但好处是,套路比较固定,如果熟悉背包的滚动数组写法,又能看出是背包模型,那么代码实现并不难
- poj 1155 TELE
- poj 3345 Bribing FIPA
- hdu 1011 Starship Troopers
- hdu 1561 The more, The Better
- zoj 3201 Tree of Tree
- uva 1407 Caves
- poj 1947 Rebuilding Roads
- hdu 4003 Find Metal Mineral
- poj 1849 Two
- poj 2486 Apple Tree
- zoj 3231 Apple Transportation
树上的支配性问题
- uva 10859 Placing Lampposts
- uva 1267 Network
- uva 10243 Fire! Fire!! Fire!!!
- ACM-ICPC Live Archive 2198 Protecting Zonk
- poj 2152 Fire
- poj 1463 Strategic game
- poj 3398 Perfect Service
- poj 3659 Cell Phone Network
树的重心 分治在树上的应用
关系树的重心的一些基本概念和定义:
- 如果只是单纯求树的重心,那是比较简单的,有固定模板可以求
- 求树的重心可以联系到分治的思想,是一类比较难的类型
其他类型
简单:
- uva 12186 Another Crisis
- hdu 2412 Party at Hali-Bula
- poj 3140 Contestants Division
- hdu 4123 Bob’s Race
- poj 3162 Walking Race
- poj 1192 最优连通子集
- poj 1935 Journey
- uva 11782 Optimal Cut