上周noip吧進(jìn)行的編程挑戰(zhàn)賽。
相關(guān)內(nèi)容見“【傳送門】百度NOIP吧編程挑戰(zhàn)賽相關(guān)帖子”
第三題是一道有依賴的背包問題。今天dev問到了，于是又回憶了一下。徐持衡大牛的集訓(xùn)隊(duì)論文中關(guān)于泛化物品的并還是不太懂。但是對這種背包有點(diǎn)了自己的感悟。
這道題目對我來說有兩個(gè)啟發(fā)點(diǎn)：
- 對多兒子的處理，用的是nlogn的預(yù)處理。
- 樹形的背包。
1.多兒子的處理
用結(jié)構(gòu)體記錄關(guān)系，a[i].root是第i個(gè)關(guān)系的父節(jié)點(diǎn)，a[i].num是第i個(gè)關(guān)系的子節(jié)點(diǎn)。將數(shù)組按root排序。然后用t[i]記錄i這個(gè)點(diǎn)的兒子在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個(gè)點(diǎn)的子節(jié)點(diǎn)在a中的位置就是從t[i]到t[i+1]-1。
免去了鏈表的繁瑣，效率還相當(dāng)高。
2.樹形的背包
主要思想就是對于i的節(jié)點(diǎn)s，f[s]強(qiáng)制賦值為f[i]，然后強(qiáng)制加入w[s],對s進(jìn)行處理，再更新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: }
相當(dāng)棒的解決問題。
3.一些習(xí)題
- CTSC98-選課