首页 > 其他分享 >E74 树形DP P4657 [CEOI2017] Chase

E74 树形DP P4657 [CEOI2017] Chase

时间:2024-11-01 21:59:51浏览次数:1  
标签:P4657 int CEOI2017 树形 long DP E74

视频链接:E74 树形DP P4657 [CEOI2017] Chase_哔哩哔哩_bilibili

 

 

P4657 [CEOI2017] Chase - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// 树形DP O(n*m)
#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N=100010,M=110;
int idx,head[N];
struct E{int to,ne;}e[N<<1];
void add(int x,int y){
  e[++idx]={y,head[x]},head[x]=idx;
}
int n,m;
LL a[N],s[N],f[N][M],g[N][M],ans;

void dfs(int u,int fa){
  vector<int> stk;
  for(int i=head[u];i;i=e[i].ne){
    int v=e[i].to;
    if(v==fa) continue;
    dfs(v,u);
    stk.push_back(v);
  }
  for(int i=1;i<=m;++i) f[u][i]=s[u],g[u][i]=s[u]-a[fa];
  for(int v:stk){
    for(int i=0;i<=m;++i) ans=max(ans,f[u][i]+g[v][m-i]);
    for(int i=1;i<=m;++i)
      f[u][i]=max(f[u][i],max(f[v][i],f[v][i-1]+s[u]-a[v])),
      g[u][i]=max(g[u][i],max(g[v][i],g[v][i-1]+s[u]-a[fa]));
  }
  for(int i=1;i<=m;++i) f[u][i]=s[u],g[u][i]=s[u]-a[fa];
  reverse(stk.begin(),stk.end());
  for(int v:stk){
    for(int i=0;i<=m;++i) ans=max(ans,f[u][i]+g[v][m-i]);
    for(int i=1;i<=m;++i)
      f[u][i]=max(f[u][i],max(f[v][i],f[v][i-1]+s[u]-a[v])),
      g[u][i]=max(g[u][i],max(g[v][i],g[v][i-1]+s[u]-a[fa]));
  }
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
  for(int i=1,x,y;i<n;++i){
    scanf("%d%d",&x,&y);
    add(x,y),add(y,x);
    s[x]+=a[y],s[y]+=a[x];
  }
  dfs(1,0);
  printf("%lld\n",ans);
}

 

// 树形DP O(n*m)
#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N=100010,M=110;
int idx,head[N];
struct E{int to,ne;}e[N<<1];
void add(int x,int y){
  e[++idx]={y,head[x]},head[x]=idx;
}
int n,m,stk[N];
LL a[N],s[N],f[N][M],g[N][M],ans;

void dfs(int u,int fa){
  for(int i=head[u];i;i=e[i].ne){
    int v=e[i].to;
    if(v!=fa) dfs(v,u);
  }
  
  int top=0;
  for(int i=head[u];i;i=e[i].ne){
    int v=e[i].to;
    if(v!=fa) stk[++top]=v;
  }
  
  for(int i=1;i<=m;++i) f[u][i]=s[u],g[u][i]=0;
  for(int i=1;i<=top;i++){
    int v=stk[i];
    for(int j=0;j<=m;++j) ans=max(ans,f[u][j]+g[v][m-j]);
    for(int j=1;j<=m;++j)
      f[u][j]=max(f[u][j],max(f[v][j],f[v][j-1]+s[u]-a[v])),
      g[u][j]=max(g[u][j],max(g[v][j],g[v][j-1]+s[u]-a[fa]));
  }
  for(int i=1;i<=m;++i) f[u][i]=s[u],g[u][i]=0;
  for(int i=top;i>=1;i--){
    int v=stk[i];
    for(int j=0;j<=m;++j) ans=max(ans,f[u][j]+g[v][m-j]);
    for(int j=1;j<=m;++j)
      f[u][j]=max(f[u][j],max(f[v][j],f[v][j-1]+s[u]-a[v])),
      g[u][j]=max(g[u][j],max(g[v][j],g[v][j-1]+s[u]-a[fa]));
  }
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
  for(int i=1,x,y;i<n;++i){
    scanf("%d%d",&x,&y);
    add(x,y),add(y,x);
    s[x]+=a[y],s[y]+=a[x];
  }
  dfs(1,0);
  printf("%lld\n",ans);
}

 

标签:P4657,int,CEOI2017,树形,long,DP,E74
From: https://www.cnblogs.com/dx123/p/18511469

相关文章

  • leetcode74 搜索二维矩阵
    leetcode74搜索二维矩阵思路可以使用二叉搜索,首先先看标准的闭区间二叉搜索代码publicintqSearch(int[]a,intl,intr,inttarget){intmid=(l+r)/2;if(l>r)returnl;//终止条件,区间为空if(a[mid]==target)returnmid;elseif(a[mid]<target)retur......
  • 洛谷题单指南-常见优化技巧-P4653 [CEOI2017] Sure Bet
    原题链接:https://www.luogu.com.cn/problem/P4653题意解读:选中的灯泡中,某一类较少的总权值减去灯泡数量所得到的收益最大值。解题思路:注意,此题关键是:要使得较少的收益最大化1、要最大化,意味着每次应该选择尽可能大权值的灯泡2、要使A、B类中较少的收益最大化,意味着每次应该优......
  • P4655 [CEOI2017] Building Bridges
    题意思路设\(sum_i=\sum\limits_{j=1}^iw_j\)。可以得到转移方程\(f_i=f_j+(h_i-h_j)^2+sum_i-sum_j\)。转化为\(y=kx+b\)的形式:\(f_i=f_j+(h_i-h_j)^2+sum_i-sum_j=f_j+h_i^2+h_j^2-2h_ih_j+sum_i-sum_j=(-2h_ih_j)+......
  • P4653 [CEOI2017] Sure Bet
    上链接[CEOI2017]SureBet题目描述现在有$n$个A类灯泡和$n$个B类灯泡,每个灯泡都有各自的权值。我们将这些灯泡分为$n$组,每组包含一个来自A类的灯泡和一个来自B类的灯泡。你可以从中选取任意个灯泡,每选取一个灯泡需要花费$1$的代价。在你选取完之后,系统会随机在A类......
  • C121 李超树+DP P4655 [CEOI2017] Building Bridges
    视频链接:C121李超树+DPP4655[CEOI2017]BuildingBridges_哔哩哔哩_bilibili   LuoguP4655[CEOI2017]BuildingBridges#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;#definelllonglong#definelsu<<......
  • [LeetCode Hot 100] LeetCode74. 搜索二维矩阵
    题目描述思路:二维矩阵坐标变换+二分查找二维矩阵坐标变换:只要知道二维数组的的行数m和列数n,二维数组的坐标(i,j)可以映射成一维的index=i*n+j;反过来也可以通过一维index反解出二维坐标i=index/n,j=index%n。(n是列数)把二维数组matrix的元素访问抽象成在......
  • Luogu-P4654-[CEOI2017] Mousetrap
    前言模拟赛之后被胁迫上去讲这题,没怎么准备,然后就在几个省的OIer面前当小丑。。倒是把我自己讲得很明白,但感觉对其他人不是很负责任,就来赎罪一下。。更好的阅读体验。题意题目链接。分析以\(t\)为根,我们的目的是让老鼠走到根的操作数最小。观察老鼠的动向,显然老鼠......
  • [CEOI2017] Mousetrap
    [CEOI2017]Mousetrap策略其实比较好想但是把式子列出来有点难。不妨把陷阱房作为根,这样就只用把老鼠往上赶。设起始房为st,陷阱房为ed。考虑st是ed的子节点,老鼠不可能送死所以会往子节点走,而管理员的最优策略是老鼠边走边堵。直到老鼠动不了时,设在节点x,把x到......
  • CEOI2017 Building Bridges
    小清新斜率优化题。分段问题显然dp,令\(f_i\)为将第\(1\)根柱子和第\(i\)根柱子连接的最小代价。\(f_1=0\),每次枚举\(i\)向前直接连接的柱子:\[f_{i}=\min\limits_{j=1}^{i-1}\left\{f_j+(h_i-h_j)^2+\sum\limits_{k=j+1}^{i-1}w_k\right\}\]令\(s_{i}=\sum\limits_{j=......
  • 台达PLC与三菱E740或D700变频器modbus 通讯案例 配件:台达DVP系列PLC,
    台达PLC与三菱E740或D700变频器modbus通讯案例配件:台达DVP系列PLC,三菱E740或者d700变频器,昆仑通态触摸屏和威纶通触摸屏功能:实现PLC与变频器进行modbus通讯,触摸屏控制启停,设置设定频率,加减速时间读取实际频率,电压,电流。说明:程序带注释,资料全程序可以直接用于现场生产。YID:7725......