本文共 1370 字，大约阅读时间需要 4 分钟。
/* 题目链接：http://poj.org/problem?id=2152 题意：城市树形分布，每个城市修建消防站的有一个花费值cost，且，当该地着火，离他最近的那个消防站必须小于 need，问要保证每个地方都能得到安全防护，需要的最小花费为？ 解题思路：令dp[i][j]为，保护i点的消防站修建在j点且以i为根节点，所有孩子即自己都能得到保护的的最小花费 状态转移方程：dp[i][j]=w[j]+sum(min(dp[child][j]-w[j],best[child])); 转载： 非常非常好的一道树状DP！ 问题描述： Z国有n个城市，从1到n给这些城市编号。城市之间连着高速公路，并且每两个城市之间有且只有一条通路。不同的高速公路可能有不同的长度。最近Z国经常发生火灾，所以当地政府决定在某些城市修建一些消防站。在城市k修建一个消防站须要花费大小为的费用。函数W对于不同的城市可能有不同的取值。如果在城市k没有消防站，那么它到离它最近的消防站的距离不能超过。每个城市在不超过距离的前提下，必须选择最近的消防站作为负责站。函数D对于不同的城市可能有不同的取值。为了节省钱，当地政府希望你用最少的总费用修建一些消防站，并且使得这些消防站满足上述的要求。 设： f[i][j]：表示以i为根的子树里修建一些消防站，并在节点j处修建一消防站，i的负责站必须是j best[i]：表示以i为根的子树的所有节点都有负责站的最小花费 dist[i]表示i到x的距离，所以没换一个节点，都要再求一次dist[]。 好了下面说下转移方程： 首先选定一个节点（x）为根 ，遍历所有节点 如果d[x]<dist[i]，则i点不可能成为x的负责站f[x][i]=INF; 如果d[x]>=dist[i]，则i可以成为x的负责站，分三种情况讨论：（y是x的儿子） A. 当i在以x为根的子树外时，对于x的每个儿子y都有两种选择：选择以y为根的子树内或外的消防站为负责站。当选择以y为根的子树内的消防站为负责站时，其子树所需的最少费用为best[y]，当选择以y为根的子树外的消防站为负责站时，y只可以选择i上的消防站作为负责站，此时其子树所需的最少费用为f[k][i]。综上得到 f[x][i]+=min(best[y],f[y][i]); (其实这块是反过来想的，当i点在x为根的子树外时，如果的x的儿子y选择i作为负责站，那么在i节点与y节点中间的x就一定是选择i了。) B. 当x==i时，x的每个儿子的选择情况与A中的一样。此时还要加上修建x上的消防站的费用。因此 f[x][i]+=w[x]+min(best[y],f[y][i]); C. 当x!=i并且i在以x为根的子树内时，此时i必定在x的某个儿子y的子树里。对于x的每个不是y的儿子其选择情况与⑴中的一样，而对于y，它只能选择j作为负责站。综上得到 f[x][i]+=f[y][i]+min(best[k],f[k][i]);(k是x中不是y的所有儿子) */#include#include #define MAXN 1005#define MAXE 2005#define INF 100000000#define min(a,b) ((a