提供一种复杂度严格 $O(n \times m)$ 的计算方式
size合并可以以将复杂度控制在 $O(n \times \sum v_i)$(不太清楚,但是可能能优化)
但对于有依赖的背包来说,还有更优的方案。
一、显性做法:
先将依赖树按照dfn排序。
然后转化成序列问题:
考虑到当前已经到了dfs序为i的节点,如果选该子树,则必须选根,先选一个:
f[i]=f[i+1][j-v[i]]+w[i]
如果不选该子树:则为
f[i]=f[i+sz[i]]
二者取max即可。
二、隐形做法
直接再dfs的过程中完成转移
先将从根父亲到当前节点(进入前)的背包复制下来。
int g[],g[i]=f[i];
然后选上当前节点,递归子树
f[j]=j>=v[u]?f[j-v[u]]+w[u]:-inf
注意必须要将不合法情况定为极小值,否则可能参与转移
由于可能不选当前子树,因此和到进入前取max
f[i]=max(f[i],g[i])
第一种写法的ac代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10,M=N*2;
vector<int> e[N];
int dfn[N],sz[N],ts;
int seq[N];
int w[N],v[N];
int f[N][N];
int n,m;
int root;
void dfs(int u)
{
dfn[u]=++ts,sz[u]=1,seq[dfn[u]]=u;
for(auto v:e[u])
{
dfs(v);
sz[u]+=sz[v];
}
}
int main()
{
cin>>n>>m;
for(int i=1,p;i<=n;i++)
{
cin>>v[i]>>w[i]>>p;
if(p==-1) root=i;
else e[p].push_back(i);
}
dfs(root);
for(int i=n;i>=1;i--)
{
int u=seq[i];
for(int j=m;j>=v[u];j--) f[i][j]=f[i+1][j-v[u]]+w[u];//选当前物品
for(int j=m;j>=0;j--) f[i][j]=max(f[i][j],f[i+sz[u]][j]);
}
cout<<f[1][m];
return 0;
}
用时:22ms
第二种写法的ac代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10,M=N;
vector<int> e[N];
int v[N],w[N];
int f[M];
int n,m,root;
void dfs(int u)
{
int g[M];
for(int j=0;j<=m;j++) g[j]=f[j];
for(int j=m;j>=v[u];j--) f[j]=f[j-v[u]]+w[u];
for(int j=v[u]-1;j>=0;j--) f[j]=-1e9;
for(auto v:e[u]) dfs(v);
for(int j=m;j>=0;j--) f[j]=max(f[j],g[j]);
}
int main()
{
cin>>n>>m;
for(int i=1,p;i<=n;i++)
{
cin>>v[i]>>w[i]>>p;
if(p==-1) root=i;
else e[p].push_back(i);
}
dfs(root);
cout<<f[m];
return 0;
}
用时:17ms
$\texttt{Orz}$