文件名称：题目求解-动态规划-树型DP经典课件
文件大小：4.26MB
文件格式：PPT
更新时间：2024-05-14 23:11:50
动态规划
题目求解 把房间看成点，房间A能到房间B，则有A向B建一条有向边，最后会形成一个有向图。图中在同一强连通分量中的点，肯定会同时选取，所以可以将强连通分量缩点，形成有向树或森林，问题变成了在树上找一个点出发，能得到的最大收益。我们在树上做一次DP即可。 由于R、C都很大，建图时，一行或一列的传送门同种类型的点之间都向第一个点建双向边，第一个点向其它类型的点建边。