HDU 5815

题意：

　　王国地图为 n 个节点的根树，首都为 1，

　　m 个旅行家要去不同的终点旅游，他们分别有各自的预算，如果路上总费用超过预算就不去了

　　给每条路定价，让赚的钱最多

分析：

　 DP[i][j]表示当从首都到城市i的路径花费为j时，以i为根的子树中的点作为目的城市的旅行者的最大花费.

　　只需要考虑j值等于0或等于某位旅行者预算的情况，所以dp的状态数是O(NM)的.

　　状态转移方程式：

　　DP[i][j] = j* n(i,j) + ∑max(DP[k][ji]) (ji >= j) 　　　　

　　　　( n(i,j)为以i作为目标城市且预算不小于j的旅行者数量，

　　　　 k 为 i 的所有子代节点

　　　　 max(DP[k][ji]) 为节点k的所有ji >= j 的 DP[k][ji] 的最大值 )

　　上式max(DP[k, ji]) (ji >= j) 可用 DP[i][j] = max(DP[i][j], DP[i][j+1]) 递推而得则转移方程式为： DP[i][j] = j* n(i,j) + DP[i][j].

　　确定完每一点的最大花费总和后，两点的最大花费总和相减即为该边的定价

　　注意起点的花费一定为 0 ！

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <vector>
 5 #include <algorithm>
 6 using namespace std;
 7 #define LL long long
 8 const int MAXN = 1005;
 9 int t, n, m, s;
10 vector<int> mp[MAXN], id[MAXN];
11 LL dp[MAXN][MAXN];
12 LL v[MAXN];
13 int edge[MAXN][MAXN];
14 int bst[MAXN][MAXN];
15 LL ans[MAXN];
16 LL a[MAXN];
17 void DFS(int x,int fa)
18 {
19     for (int i = 0; i < mp[x].size(); i++)
20     {
21         if (mp[x][i] != fa) DFS(mp[x][i], x);
22     }    
23     for (int j = s-1; j >= 0; j--)
24     {
25         int t = 0;
26         for (int i = 0; i < id[x].size(); i++)
27             if (a[id[x][i]] >= v[j]) t++;
28         dp[x][j] += t*v[j];                         //j* n(i,j) 
29         for (int i = 0; i < mp[x].size(); i++)
30         {
31             if (mp[x][i] == fa) continue;
32             int p = mp[x][i];
33             dp[x][j] += dp[p][j];
34         }    
35         if (j == s-1 || dp[x][j+1] <= dp[x][j])
36         {
37             bst[x][j] = j;
38         }
39         else
40         {
41             dp[x][j] = dp[x][j+1];
42             bst[x][j] = bst[x][j+1];
43         }
44     }
45 }
46 void DFS2(int x,int a,int fa)
47 {
48     for (int i = 0; i < mp[x].size(); i++)
49     {
50         int e = mp[x][i];
51         if (e == fa) continue;
52         int b = bst[e][a];
53         ans[edge[x][e]] =v[b]- v[a];
54         DFS2(e,b,x);
55     }
56 }
57 int main()
58 {
59     scanf("%d", &t);
60     while (t--)
61     {
62         scanf("%d%d", &n, &m);
63         for (int i = 1; i <= n; i++) mp[i].clear(), id[i].clear();
64         memset(dp,0,sizeof(dp));
65         for (int i = 1; i < n ;i++)
66         {
67             int u,v; scanf("%d%d", &u, &v);
68             mp[u].push_back(v); 
69             mp[v].push_back(u);
70             edge[u][v] = edge[v][u] = i;
71         }
72         for (int i = 1; i <= m; i++)
73         {
74             int u; scanf("%d%lld",&u, &a[i]);
75             v[i] = a[i];
76             id[u].push_back(i);
77         }
78         id[1].clear();//起始点不计费!
79         v[0] = 0;
80         sort(v,v+1+m);
81         s = unique(v,v+1+m) - v;
82         DFS(1,-1);
83         DFS2(1,0,-1);
84         printf("%lld
",dp[1][0]);
85         for (int i = 1; i < n-1; i++)
86             printf("%lld ",ans[i]);
87         printf("%lld
", ans[n-1]);
88     }
89 }

我自倾杯，君且随意