文件名称：网络收费NOI-动态规划-树型DP经典课件
文件大小：4.26MB
文件格式：PPT
更新时间：2024-05-14 23:11:51
动态规划
网络收费NOI2006 给了你一棵满二叉树（共2^N个结点）,每个叶节点有一个类型(A或B),任意两个叶节点有一个流量Fij,他们的花费就是k* Fij ,k为系数，由这两个叶子结点的最近公共祖先P为根的子树中所有叶节点中A类型和B类型的点的个数来确定。现在你可以改变每个叶节点的类型,需要花费Ci ,任务是使所有花费之和最小。 数据规模和约定 40%的数据中N≤4； 80%的数据中N≤7； 100%的数据中N≤10,0≤Fij≤500,0≤Ci≤500 000