文件名称：迷失游乐园NOI-动态规划-树型DP经典课件
文件大小：4.26MB
文件格式：PPT
更新时间：2024-05-14 23:11:50
动态规划
迷失游乐园（NOI2012） 给定一个n点、m条边的无向连通图。小Z随机从某个点出发，每次随机等概率地去一个和当前点有边的点，并且同一个点不去两次（包括起始点）。这个过程一直进行，直到当前点的所有相邻点都已经访问过为止。小Z所有经过的点按顺序构成一条非重复路径，他想知道这条路径的期望长度是多少？ 数据规模： 对50%的数据 ：m=n-1; 另外50%的数据，m=n,且环上点数不超过20; 100%的数据有n<=10^5。