个人网站建设规划案例,西安搜建站科技网站,营销型网站设计稿,保定网站制作软件M. Monster Hunter
才知道原来树形dp是三维的#xff0c;一直没有学会过#xff0c;感谢大佬的文章#xff01;算法进阶—理解树形背包问题
状态表示#xff1a;fi,k,j,{0/1}f_{i,k,j,\{0/1\}}fi,k,j,{0/1}以iii为根的子树#xff0c;考虑到第kkk个儿子时#xff0c;…M. Monster Hunter
才知道原来树形dp是三维的一直没有学会过感谢大佬的文章算法进阶—理解树形背包问题
状态表示fi,k,j,{0/1}f_{i,k,j,\{0/1\}}fi,k,j,{0/1}以iii为根的子树考虑到第kkk个儿子时使用了jjj次魔法自己是否被魔法干掉的最小花费。
状态转移 fi,k,ab,0fi,k−1,a,0min(fv,cnt,b,0av,fv,cnt,b,1)f_{i,k,ab,0}f_{i,k-1,a,0}\min(f_{v,cnt,b,0}a_{v},f_{v,cnt,b,1})fi,k,ab,0fi,k−1,a,0min(fv,cnt,b,0av,fv,cnt,b,1) fi,k,ab,1fi,k−1,a,1min(fv,cnt,b,0,fv,cnt,b,1)f_{i,k,ab,1}f_{i,k-1,a,1}\min(f_{v,cnt,b,0},f_{v,cnt,b,1})fi,k,ab,1fi,k−1,a,1min(fv,cnt,b,0,fv,cnt,b,1)
对于第2维可以使用滚动数组优化掉然后就变成了常见的树形dp模式
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includestack
#includequeue
#includebitset
#includerandom
#includebitset
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
#includeunordered_set
using namespace std;
typedef long long ll;
typedef pairll,int pli;
typedef pairint,int pii;
const ll mod1e97;
const int N2010;
int h[N],e[N],ne[N],idx;
void add(int a,int b)
{e[idx]b,ne[idx]h[a],h[a]idx;
}
ll f[N][2][N][2];
ll a[N];
int sz[N],cnt[N];
int n;
// f[i][k][j][0/1] 以i为根的子树前k个儿子使用了j次魔法i节点是否使用魔法的最小化代价
void dfs(int u)
{ f[u][0][0][0]a[u];f[u][0][1][1]0;sz[u]1;for(int ih[u];i!-1;ine[i]){int sone[i];dfs(son);cnt[u];for(int j0;jsz[u];j)f[u][cnt[u]1][j][1]f[u][cnt[u]1][j][0]1e18;for(int j0;jsz[u];j)for(int k0;ksz[son];k){f[u][cnt[u]1][jk][1]min(f[u][cnt[u]1][jk][1],f[u][cnt[u]-11][j][1]f[son][cnt[son]1][k][0]);f[u][cnt[u]1][jk][1]min(f[u][cnt[u]1][jk][1],f[u][cnt[u]-11][j][1]f[son][cnt[son]1][k][1]);f[u][cnt[u]1][jk][0]min(f[u][cnt[u]1][jk][0],f[u][cnt[u]-11][j][0]f[son][cnt[son]1][k][0]a[son]);f[u][cnt[u]1][jk][0]min(f[u][cnt[u]1][jk][0],f[u][cnt[u]-11][j][0]f[son][cnt[son]1][k][1]);}sz[u]sz[son];}
}
int main()
{int T;cinT;while(T--){idx0;cinn;for(int i0;in;i) sz[i]0,cnt[i]0,h[i]-1;for(int i0;in;i)for(int j0;jn;j)f[i][0][j][0]f[i][1][j][0]f[i][0][j][1]f[i][1][j][1]1e18;for(int i2;in;i){int p;cinp;add(p,i);}for(int i1;in;i) cina[i];dfs(1);for(int i0;in;i)coutmin(f[1][cnt[1]1][i][0],f[1][cnt[1]1][i][1]) ;cout\n;}
}经过这道题自己对树形dp有了一个重新的认识明天多做几个树形dp干翻树形dp
要加油哦~
