[关闭]
@Junlier 2018-10-31T19:10:47.000000Z 字数 1618 阅读 2035

BZOJ 4033: [HAOI2015]树上染色题解(树形dp)

题解
阅读体验:https://zybuluo.com/Junlier/note/1327400
原题地址:
BZOJ 4033: [HAOI2015]树上染色题解
洛谷 P3177 [HAOI2015]树上染色
应该各大都有。。。可以多倍经验。。。

一眼树形是吧
因为要选出个黑点,所以知道子树内有多少个黑点,就知道子树外有多少个黑点
那么设dp[now][j]表示在的子树内选了个黑点对答案的贡献
考虑每条边对答案的贡献进行
枚举已经处理完的子树选出了个,当前处理的子树选出了
一定有 (是当前节点,是子树节点,now-qw边对答案的贡献)

dp[now][j+k]=MAX(dp[now][j+k],dp[now][j]+dp[qw][k]+Val);

那么怎么算出呢,这个不难

Val=k*(K-k)*w+(siz[qw]-k)*(n-K-siz[qw]+k)*w;
子树黑点数×外面黑点数×边权        子树白点数×外面白点数×边权

那么这个题目不就很简单吗。。。然而手写MAX忘记开long long Wa了很久

  1. #include<bits/stdc++.h>
  2. #define il inline
  3. #define rg register
  4. #define ldb double
  5. #define lst long long
  6. #define rgt register int
  7. #define N 2050
  8. #define qw ljl[i].to
  9. using namespace std;
  10. const int Inf=1e9;
  11. il lst MAX(rg lst x,rg lst y){return x>y?x:y;}
  12. il int MIN(rgt x,rgt y){return x<y?x:y;}
  13. il lst read()
  14. {
  15. rg lst s=0,m=0;char ch=getchar();
  16. while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
  17. while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  18. return m?-s:s;
  19. }
  20. int n,K,Rt;
  21. int hd[N],siz[N],cnt;
  22. lst dp[N][N];//The MAX contribution of [At now][got j black points]
  23. struct EDGE{int to,nxt,v;}ljl[N<<1];
  24. il void Add(rgt p,rgt q,rgt o){ljl[++cnt]=(EDGE){q,hd[p],o},hd[p]=cnt;}
  25. void Dfs(rgt now,rgt fm)
  26. {
  27. siz[now]=1;
  28. for(rgt i=hd[now],w;i;i=ljl[i].nxt)
  29. {
  30. if(qw==fm)continue;Dfs(qw,now),w=ljl[i].v;
  31. for(rgt j=MIN(siz[now],K);j>=0;--j)
  32. for(rgt k=MIN(siz[qw],K-j);k>=0;--k)
  33. {
  34. rg lst Val=1LL*k*(K-k)*w+1LL*(siz[qw]-k)*(n-K-siz[qw]+k)*w;
  35. //The contribution of the edge-black&white
  36. dp[now][j+k]=MAX(dp[now][j+k],dp[now][j]+dp[qw][k]+Val);
  37. }
  38. siz[now]+=siz[qw];
  39. }
  40. }
  41. int main()
  42. {
  43. n=read(),K=read();
  44. srand(time(NULL)),Rt=rand()%n+1;
  45. for(rgt i=1;i<n;++i)
  46. {
  47. rgt p=read(),q=read(),o=read();
  48. Add(p,q,o),Add(q,p,o);
  49. }Dfs(Rt,0);
  50. printf("%lld\n",dp[Rt][K]);
  51. return 0;
  52. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注