其实早就想写了,今天考试的树形dp虽说是板子,但涉及到赋极小值问题,使原
来理解的板子被卡成20pts,主要讲一种新版板子写法.
题面:网上出现了一种高科技产品——人品测试器。只要你把你的真实姓名输
入进去,系统将自动输出你的人品指数。yzx 不相信自己的人品为 0。经过了
许多研究后,yzx 得出了一个更为科学的人品计算方法。这种方法的理论依据
是一个非常重要的结论:人品具有遗传性。因此,一个人的人品完全由他的祖先
决定。yzx 提出的人品计算方法相当简单,只需要将测试对象的 k 个祖先的人
品指数(可能为负数)加起来即可。选择哪 K 个祖先可以由测试者自己决定,但
必须要满足这个要求:如果除自己的父母之外的某个祖先被选了,那么他的下
一代必需要选(不允许跳过某一代选择更远的祖先,否则将失去遗传的意义)。
非常不幸的是,yzx 测试了若干次,他的人品值仍然不能为一个正数。现在 yz
x 需要你帮助他找到选择祖先的最优方案,使得他的人品值最大。
注意:1.祖先并非有两个儿子 2.有负点权.
ps:1.普通树形dp要提前对f赋极小值应对负点权 2.不用构造0的虚点,直接选择不建边,非pa[fa][son]的形式.
在代码中f[x][len] 表示在x点扩展len条边(点)得到最优值,用背包的思维理解.
upd:1.对于代码中的for中的min相当于状态压缩,即分配的最大背包容量.
2.注意取max中的f[ fa][ j-k -1] 是指除了son 即它所选边fa能在其他子树选j-k-1条边的最优值.
这里的背包思想是来应对多叉树
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define R register #define ll long long const int maxn=1010; long long n,m,fx,fy,cnt,f[maxn][maxn],val[maxn],size[maxn],head[maxn]; struct bian{ ll to,next,v; }len[maxn<<2]; inline long long fd() { long long s=1,t=0; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') s=-1; c=getchar(); } while(c>='0'&&c<='9') { t=t*10+c-'0'; c=getchar(); } return s*t; } void add(ll from,ll to,ll v) { len[++cnt].to=to; len[cnt].v=v; len[cnt].next=head[from]; head[from]=cnt; } void dp(ll x,ll fa) { for(R ll k=head[x];k;k=len[k].next) { ll to=len[k].to; if(to==fa) continue; dp(to,x); size[x]+=size[to]+1; for(R ll i=min(size[x],m);i>=0;--i) for(R ll j=min(size[to],i-1);j>=0;--j) f[x][i]=max(f[x][i],f[x][i-1-j]+f[to][j]+len[k].v);//用背包理解. } } int main() { freopen("rpwt.in","r",stdin); freopen("rpwt.out","w",stdout); n=fd(),m=fd(); for(R ll i=2;i<=n;++i) val[i]=fd(); for(R ll i=1;i<=n;++i) fill(f[i]+1,f[i]+1+n,-19260817); for(R ll i=1;i<=n;++i) { fx=fd(),fy=fd(); if(fx) add(i,fx,val[fx]),add(fx,i,val[fx]); if(fy) add(i,fy,val[fy]),add(fy,i,val[fy]); } dp(1,1); printf("%lld",f[1][m]); return 0; }