樹形依賴背包——百度NOIP吧編程挑戰賽"charge"
上周noip吧進行的編程挑戰賽。
相關內容見“【傳送門】百度NOIP吧編程挑戰賽相關帖子”
第三題是一道有依賴的背包問題。今天dev問到了,于是又回憶了一下。徐持衡大牛的集訓隊論文中關于泛化物品的并還是不太懂。但是對這種背包有點了自己的感悟。
這道題目對我來說有兩個啟發點:
- 對多兒子的處理,用的是nlogn的預處理。
- 樹形的背包。
1.多兒子的處理
用結構體記錄關系,a[i].root是第i個關系的父節點,a[i].num是第i個關系的子節點。將數組按root排序。然后用t[i]記錄i這個點的兒子在a中的起始位置。
1: struct ss2: {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.一些習題
posted on 2010-08-27 17:25 Sephiroth Lee 閱讀(1019) 評論(1) 編輯 收藏 引用 所屬分類: 信息奧賽

