ZigZagK的博客
[树形DP]LOJ2485(CEOI2017)【Chase】题解
[树形DP]LOJ2485(CEOI2017)【Chase】题解
2018年8月19日 22:40
LOJ
查看标签

题目概述

有 $n$ 个点的树,每个点上有 $p_i$ 只咕咕咕。从任意点出发开始走,有 $k$ 次放面包的机会,放下面包后相邻点的咕咕咕就会凑到该点,问先走一遍之后再走一遍遇到的咕咕咕个数之差最大是多少。

解题报告

考虑已知从哪个点出发,那么每个点放不放面包的贡献是固定的,与上一个点有没有放面包无关(上一个点放面包这个点再来一次又凑过来了……),所以 $O(n^2log_k)$ 贪心很显然。

不过这个很像求直径啊,考虑树形DP。由于有方向所以记录 $f[i][j]$ 表示向上走到 $i$ ,放了 $j$ 次面包,再记录 $g[i][j]$ 表示向下走到 $i$ ,放了 $j$ 次面包。

树形DP很容易写丑……Orz%%%KCZ,写的超级简洁。大概就是每个点儿子正着做一遍,反着做一遍(因为路径有方向,所以要正反都做)。

示例程序

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const int maxn=100000,maxm=100; int n,m,a[maxn+5];LL sum[maxn+5],f[maxn+5][maxm+5],g[maxn+5][maxm+5],ans; int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5],now[maxn+5]; #define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E) void DP(int x,int y,int pre){ for (int j=0;j<=m;j++) ans=max(ans,f[x][j]+g[y][m-j]); for (int j=1;j<=m;j++) f[x][j]=max(f[x][j],max(f[y][j],f[y][j-1]+sum[x]-a[y])); for (int j=1;j<=m;j++) g[x][j]=max(g[x][j],max(g[y][j],g[y][j-1]+sum[x]-a[pre])); } void Dfs(int x,int pre=0){ memset(f[x],0,sizeof(f[x]));memset(g[x],0,sizeof(g[x]));f[x][1]=sum[x];g[x][1]=sum[x]-a[pre]; for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x),DP(x,son[j],pre); ans=max(ans,max(f[x][m],g[x][m]));now[0]=0; for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) now[++now[0]]=son[j]; memset(f[x],0,sizeof(f[x]));memset(g[x],0,sizeof(g[x]));f[x][1]=sum[x];g[x][1]=sum[x]-a[pre]; for (int i=now[0];i;i--) DP(x,now[i],pre);ans=max(ans,max(f[x][m],g[x][m])); } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),sum[x]+=a[y],sum[y]+=a[x],Add(x,y),Add(y,x); Dfs(1);return printf("%lld\n",ans),0; }
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
本文写于 2422 天前,最后更新于 2421 天前。
部分信息可能已经过时,博主也可能已经无法对其内容进行解答。
OK
  1. 1 Skyscape Plum - Melodic Artist
  2. 2 ほしのおとしもの ああああ
  3. 3 感情の摩天楼 ~ Cosmic Mind 上海アリス幻樂団
  4. 4 秘匿されたフォーシーズンズ 上海アリス幻樂団
  5. 5 Ideal and the Real 小西利樹
  6. 6 Undertale Toby Fox
  7. 7 First Steps Lena Raine
  8. 8 Mirror Temple (Mirror Magic Mix) Lena Raine / 2 Mello
  9. 9 City of Tears Christopher Larkin
  10. 10 Tower Of Heaven (You Are Slaves) Feint
Skyscape - Plum - Melodic Artist
00:00 / 00:00
An audio error has occurred, player will skip forward in 2 seconds.

作曲 : Jeong Min Jae

纯音乐,请欣赏