算是我的第一个树形DP 的题：
题目意思：N个城市形成树状结构。现在建立一些消防站在某些城市；每个城市有两个树形cost（在这个城市建立消防站的花费），limit ；
我们要是每个城镇都是安全的：就是每个距离这个城镇最近的消防站不能超过这个城镇的limit值；
解法：这个题目乍一看卧槽怎么玩！玩不了啊！先给出dp[i][j]( I 依靠J，并且 I 这课子树都已经被覆盖的最优解（不一定都被J覆盖）)；
假设一个节点的亲儿子树都被解决完毕,我们对于这些 亲儿子树 和这个 节点所组成的树的解如何得出？
初始化dp[i][j]=cost[j];
无疑使枚举这个节点I 依靠的节点，然后得出最小值;
而这些 亲子树的合并无疑有俩情况
1：这些亲儿子树依靠这个节点J 值 dp[k][j]-cost[j];
2：这些亲儿子树不依靠这个节点I 值
{
int best=0x7fffffff;
for（int w=1;w<=n;w++）
best=min(dp[k][w],best);
>>>best;
}
所以我们要开一个数字组维护每个节点的最值；
我输得不清楚那么百度下“国家集训队2006论文集 陈启峰”
#include <cstdio> #include <algorithm> #include <cmath> #include <cstdlib> #include <cstring> using namespace std; const int maxn=1004; const int INF=0x7fffffff; struct Edge { int to,dis,pre; Edge(int to=0,int dis=0,int pre=0):to(to),dis(dis),pre(pre){} }; Edge edge[maxn*2]; int head[maxn],pos; int dp[maxn][maxn]; int dis[maxn][maxn]; int limit[maxn],cost [maxn]; int best[maxn]; int n,start; void inint() { for(int i=1;i<maxn;i++) { best[i]=INF; for(int j=1;j<maxn;j++) dp[i][j]=INF; } memset(head,-1,sizeof(head)); pos=0; } void add_edge(int s,int to,int dis) { edge[pos]=Edge(to,dis,head[s]); head[s]=pos++; } void DIS(int pa,int s) { for(int i=head[s];~i;i=edge[i].pre) { Edge &tmp=edge[i]; if(tmp.to==pa)continue; dis[start][tmp.to]=dis[start][s]+tmp.dis; DIS(s,tmp.to); } } void dfs(int pa,int s) { for(int i=head[s];~i;i=edge[i].pre) { Edge &tmp=edge[i]; if(tmp.to==pa)continue; dfs(s,tmp.to); } for(int i=1;i<=n;i++) if(dis[s][i]<=limit[s]) { dp[s][i]=cost[i]; for(int j=head[s];~j;j=edge[j].pre) { Edge &tmp=edge[j]; if(tmp.to==pa)continue; dp[s][i]+=min(dp[tmp.to][i]-cost[i],best[tmp.to]);//加等 } best[s]=min(best[s],dp[s][i]); } } int main() { int t; int a,b,c; scanf("%d",&t); while(t--) { inint(); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&cost[i]); for(int i=1;i<=n;i++)scanf("%d",&limit[i]); for(int i=2;i<=n;i++) { scanf("%d%d%d",&a,&b,&c); add_edge(a,b,c); add_edge(b,a,c); } for(int i=1;i<=n;i++)start=i,DIS(-1,i); dfs(-1,1); printf("%d ",best[1]); } return 0; }