Corporate Gifting（树形动态规划）

原题：https://www.facebook.com/hackercup/problems.php?pid=759650454070547&round=344496159068801

题意：给定一颗有根树，在树上下层的节点要给上层节点礼物，根节点的礼物则给慈善会，但是给礼物有个条件就是你不能送你的父节点已经送出的礼物。问满足要求的最少花费。 题解：这个题卡了一段时间，类似于染色问题，可以用树形动态规划求解。因为已知节点个数为N，则我们单个节点的最大花费不会超过log2（N） = 18。 1. 设dp[i][j]是在i节点花费j时以i为根节点的子树所需要的总开销。 2. 则dp[i][j] = sum{min{dp[son][k],1 <= k <= 18且k != j}，son为i的每个子节点};

比赛的时候一开始使用DFS，没注意到节点规模在树成链状时会导致暴栈。但是时间已经来不及了，很遗憾没有进入round 2。

代码如下：

;<vector<int> > sons;int N;int minCost[maxN][maxM];struct node{int ID;int depth;< (node x,node y){return x.depth > y.depth;}}employee[maxN];int BFS(){for(int i = 1;i <= N;i++){employee[i].ID = i;}employee[1].depth = 0;int now,next;int sonSize;queue<int> q;q.push(1);while(!q.empty()){now = q.front();q.pop();sonSize = sons[now].size();for(int i = 0;i < sonSize;i++){next = sons[now][i];q.push(next);employee[next].depth = employee[now].depth+1;}}}int dp(){int fa,son,sonSize;int i,j,k,m;int tmpMinCost;BFS();sort(employee+1,employee+N+1);for(i = 1;i <= N;i++){fa = employee[i].ID;sonSize = sons[fa].size();for(j = 1;j <= maxM;j++){minCost[fa][j] = j;for(k = 0;k < sonSize;k++){son = sons[fa][k];tmpMinCost = INT_MAX;for(int m = 1;m <= maxM;m++){if(m == j)continue;tmpMinCost = min(tmpMinCost,minCost[son][m]);}minCost[fa][j] += tmpMinCost;}}}int ans = INT_MAX;for(i = 1;i <= maxM;i++){ans = min(ans,minCost[1][i]);}return ans;}int main(){freopen(“corporate_gifting.txt”,”r”,stdin);freopen(“out.txt”,”w”,stdout);int T;int fa;scanf(“%d”,&T);for(int i = 1;i <= T;i++){scanf(“%d”,&N);vector<vector<int> >().swap(sons);sons.resize(N+1);for(int j = 1;j <= N;j++){scanf(“%d”,&fa);sons[fa].push_back(j);}printf(“Case #%d； %d\n”,i,dp());}return 0;}

，今天的长相厮守，只是尽力而为而已。