题解 P2515 【[HAOI2010]软件安装】
zfz04
·
·
题解
[HAOI2010]软件安装
O(nm)泛化物品优化写法
泛化物品优化详细解释请看----国家集训队2009论文集浅谈几类背包题(第十面)
代码片段：
void dfs(int x,int sum)
{
if(sum<=0) return ;
for(re int i=0,t;i<_e[x].size();i++)
{
t=_e[x][i];
for(re int j=0;j<=sum-sum_v[t];j++)/为v预留空间
dp[t][j]=dp[x][j];
dfs(t,sum-sum_w[t]);//对于v的现有空间
for(re int j=sum_w[t];j<=sum;j++)
dp[x][j]=max(dp[x][j],dp[t][j-sum_w[t]]+sum_v[t]);//背包
}
}
发现其实和01背包很像，只是在01背包的基础上限制了条件——捆绑关系；
而我对泛化物品优化的感性理解就是："预留空间"——为在 u 到到根节点的路径上的点预留空间。
这样就可以在对uDP的时候保证他所依赖的物品预先算进去了；
再结合上面的代码，我相信大家应该都可以理解。
code:
```c++
#include<iostream>
#include<cstdio>
#include<vector>
#define re register
using namespace std;
const int N=101;
int n,m;
vector<int> e[N];
vector<int> _e[N];
int sum_w[N],sum_v[N],du[N];
int w[N],v[N],dp[N][501];
int low[N],dfn[N],tot,tim,s[N],top,c[N];
inline int read()
{
int res;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
res=ch-'0';
ch=getchar();
while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+ch-'0',ch=getchar();
return res;
}
inline void tarjan(int x)
{
dfn[x]=low[x]=++tim;
s[++top]=x;
for(re int i=0,t;i<e[x].size();i++)
{
t=e[x][i];
if(!dfn[t])
{
tarjan(t);
low[x]=min(low[x],low[t]);
}
else if(!c[t]) low[x]=min(low[x],dfn[t]);
}
if(dfn[x]==low[x])
{
++tot;
while(s[top+1]!=x)
{
c[s[top]]=tot;
sum_v[tot]+=v[s[top]];
sum_w[tot]+=w[s[top]];
top--;
}
}
}
inline void dfs(int x,int sum)
{
if(sum<=0) return ;
for(re int i=0,t;i<_e[x].size();i++)
{
t=_e[x][i];
for(re int j=0;j<=sum-sum_w[t];j++)
dp[t][j]=dp[x][j];
dfs(t,sum-sum_w[t]);
for(re int j=sum_w[t];j<=sum;j++)
dp[x][j]=max(dp[x][j],dp[t][j-sum_w[t]]+sum_v[t]);
}
}
int main()
{
n=read(),m=read();
for(re int i=1;i<=n;i++) w[i]=read();
for(re int i=1;i<=n;i++) v[i]=read();
for(re int i=1,a;i<=n;i++) {a=read();if(a) e[a].push_back(i);}
for(re int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
for(re int i=1;i<=n;i++)
for(re int j=0,u,v;j<e[i].size();j++)
{
u=c[i],v=c[e[i][j]];
if(u==v) continue;
du[v]++;
_e[u].push_back(v);
}
for(re int i=1;i<=tot;i++)
if(!du[i]) _e[0].push_back(i);
dfs(0,m);
printf("%d",dp[0][m]);
return 0;
}
```
再安利一下我的[树型DP学习笔记](https://www.cnblogs.com/Wednesday-zfz/p/12209729.html)