樹形依賴背包——百度NOIP吧編程挑戰賽"charge"

上周noip吧進行的編程挑戰賽。

相關內容見“【傳送門】百度NOIP吧編程挑戰賽相關帖子”

第三題是一道有依賴的背包問題。今天dev問到了，于是又回憶了一下。徐持衡大牛的集訓隊論文中關于泛化物品的并還是不太懂。但是對這種背包有點了自己的感悟。

這道題目對我來說有兩個啟發點：

1. 對多兒子的處理，用的是nlogn的預處理。
2. 樹形的背包。

1.多兒子的處理

用結構體記錄關系，a[i].root是第i個關系的父節點，a[i].num是第i個關系的子節點。將數組按root排序。然后用t[i]記錄i這個點的兒子在a中的起始位置。

  1: struct ss
  2: {
  3:     int root,num;
  4: } a[maxn];
  5: int t[maxn];
  6: 
  7: void init()
  8: {
  9:     qsort(a,n,sizeof(ss),cmp);
 10:     for (int i=1;i<=n;++i)
 11:         if (!t[a[i].root])
 12:             t[a[i].root]=i;
 13:     t[n+1]=n+1;
 14:     for (int i=n;i>0;--i)
 15:         if (!t[i])
 16:             t[i]=t[i+1];
 17: }
 18: 

這樣第i個點的子節點在a中的位置就是從t[i]到t[i+1]-1。

免去了鏈表的繁瑣，效率還相當高。

2.樹形的背包

主要思想就是對于i的節點s，f[s]強制賦值為f[i]，然后強制加入w[s],對s進行處理，再更新f[i]。

  1: void dp(int x)
  2: {
  3:     for (int i=t[x];i<t[x+1];++i)
  4:     {
  5:         int k=a[i].num;
  6:         for (int j=0;j<=V;++j) f[k][j]=f[x][j]+w[k];
  7:         dp(k);
  8:         for (int j=v[k];j<=V;++j)
  9:             if (f[k][j-v[k]]>f[x][j])
 10:                 f[x][j]=f[k][j-v[k]];
 11:     }
 12: }

3.一些習題

1. CTSC98-選課

posted on 2010-08-27 17:25 Sephiroth Lee 閱讀(1019) 評論(1)  編輯 收藏 引用 所屬分類: 信息奧賽