算是我的第一個樹形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\n",best[1]);}return 0; }
?
)
)
