bzoj 4033 [HAOI2015]树上染色

bzoj 4033 [HAOI2015]树上染色

​​ Description 有一棵点数为N的树，树边有边权。给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并 将其他的N-K个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。 问收益最大值是多少。

Input 第一行两个整数N,K。 接下来N-1行每行三个正整数fr,to,dis，表示该树中存在一条长度为dis的边(fr,to)。 输入保证所有点之间是联通的。 N<=2000,0<=K<=N

Output 输出一个正整数，表示收益的最大值。

Sample Input 5 2 1 2 3 1 5 1 2 3 1 2 4 2 Sample Output 17 【样例解释】 将点1,2染黑就能获得最大收益。 HINT 2017.9.12新加数据一组 By GXZlegend

Source 鸣谢bhiaibogf提供

树形dp

设dp[x][i]表示在x子树内选择了i个黑点 对答案做出的贡献最大是多少

这样定义方便dp 方程很好写dp[x][i+j]=max(dp[x][i]+dp[y][j]+(ll)j*(k-j)z+(ll)(size[y]-j)(n-k-size[y]+j)*z)) y就是x的子树

仍然有一些实现的细节

乍一看应该是n^3 但是仔细想 如果只利用合法状态进行dp的话可以发现

每次相当于在子树内枚举了所有以这个点作为lca的点对状态

​

#include#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=2200;struct node{ int y,next,z;}data[N<<1];ll dp[N][N];int n,k,num,h[N],size[N];inline void dfs(int x,int fa){ size[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa) continue; dfs(y,x);size[x]+=size[y]; }dp[x][0]=dp[x][1]=0;int sum=1; for (int owo=h[x];owo;owo=data[owo].next){ int y=data[owo].y;if(y==fa) continue; int z=data[owo].z; for (int i=min(k,sum);~i;--i){ for (int j=min(k,size[y]);~j;--j){ if(i+j>k||dp[y][j]<0) continue; dp[x][i+j]=max(dp[x][i+j],dp[x][i]+dp[y][j]+(ll)j*(k-j)*z+(ll)(size[y]-j)*(n-k-size[y]+j)*z); } }sum+=size[y]; }}int main(){ freopen("bzoj4033.in","r",stdin); memset(dp,0xff,sizeof(dp)); n=read();k=read(); for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。