首页 > 其他分享 >动态规划三

动态规划三

时间：2023-08-03 14:57:57浏览次数：27  
标签：include int d2 dfs maxn 动态 规划 d1

复健\(Day4\)

动态规划（三）树形\(DP\)

树形\(DP\)一般思路：从分析子树入手，最优解通常是与子树根节点\(u\)有关的函数，状态计算就是寻找根节点与子节点以及边权的递推关系

编写代码，通常要\(DFS\)，从根到叶，再从叶到根，在合适的时候\(DP\)

\(1.\)没有上司的舞会

https://www.luogu.com.cn/problem/P1352

\(f[u][0]\)表示以\(u\)为根节点的子树，同时不包括\(u\)的快乐指数

\(f[u][1]\)表示以\(u\)为根节点的子树，同时包括\(u\)的快乐指数

故\(f[u][0]+=max(\sum f[s][0],f[s][1]),f[u][1]+=\sum f[s][0]\)

从根节点\(u\)开始\(dfs\)一遍即可

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 6010
using namespace std;

int f[maxn][2];
int w[maxn];
int s[maxn][5010],sz[maxn];
bool fa[maxn];

void dfs(int u)
{
	f[u][1]=w[u];
	for(int i=1;i<=sz[u];i++)
	{
		int v=s[u][i];
		dfs(v);
		f[u][0]+=max(f[v][0],f[v][1]);
		f[u][1]+=f[v][0];
	}
}

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		s[v][++sz[v]]=u;
		fa[u]=true;//用于找根节点
	}
	int rt=1;
	while(fa[rt]) rt++;
	dfs(rt);
	printf("%d\n",max(f[rt][0],f[rt][1]));
	return 0;
}

注意到\(s[maxn][5010]\)数组，如果两维都开\(6010\)，最后会有一个点\(MLE\)，最后不得已改成了这样反而通过了，但是如果遇到大于\(5010\)个节点而且只有一个根节点其余全是叶节点的情况等等，这是不能过的

所以还是采用\(vector\)数组去做比较好

\(2.\)树形背包（有依赖的背包）

https://www.acwing.com/problem/content/10/

\(f[u][j]\)表示以\(u\)为根节点，体积和不超过容量\(j\)时所获得的最大价值

节点\(u\)有\(i\)个子结点，每个子结点可以选也可以不选

我们可以把这\(i\)个子结点看作\(i\)组物品，每组物品\(s[i]\)按照单位体积拆分，有\(0,1,2,\cdots ,j-v[u]\)中决策（按单位体积拆分是因为\(s[i]\)的子孙可能存在体积为\(1\)的物品，拆分到\(j-v[u]\)是因为要预留出\(v[u]\)的空间装入节点\(u\)的物品

然后从根到叶进行\(dfs\)即可

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 110
using namespace std;

int f[maxn][maxn];
int v[maxn],w[maxn];
int s[maxn][maxn],sz[maxn];
int n,V;
int rt;

void dfs(int u)
{
	for(int i=v[u];i<=V;i++) f[u][i]=w[u];
	for(int i=1;i<=sz[u];i++)
	{
		int son=s[u][i];
		dfs(son);
		for(int j=V;j>=v[u];j--)
		{
			for(int k=0;k<=j-v[u];k++)
			{
				f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);
			}
		}
	}
}

int main()
{
	cin>>n>>V;
	for(int i=1;i<=n;i++)
	{
		int p;
		cin>>v[i]>>w[i]>>p;
		if(p==-1)
		{
			rt=i;
			continue;
		}
		else s[p][++sz[p]]=i;
	}
	dfs(rt);
	printf("%d\n",f[rt][V]);
}

\(3.\)树的重心

重心是指将该点删除后，在剩下的各个连通块中点数的最大值最小的点

\(size\)记录\(u\)的最大子树的节点数，\(sum\)记录以\(u\)为根的子树的节点数（包含\(u\)），那么\(n-sum\)就是\(u\)上面部分的节点数，以\(u\)为重心时，其最大子树节点数就为\(ans=max(size,n-sum)\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 110
using namespace std;

int head[maxn<<1],tot;
int ans,n;
int vis[maxn];

struct Edge
{
	int v,nxt;
	Edge(){}
	Edge(int v,int nxt):v(v),nxt(nxt){}
}ed[maxn<<1];

void add(int u,int v)
{
	ed[tot]=Edge(v,head[u]);
	head[u]=tot++;
}

int dfs(int rt)
{
	vis[rt]=1;
	int size=0,sum=1;
	for(int i=head[rt];~i;i=ed[i].nxt)
	{
		int v=ed[i].v;
		if(vis[v]) continue;
		int s=dfs(v);
		size=max(size,s);
		sum+=s;
	}
	ans=min(ans,max(size,n-sum));
	return sum;
}

int main()
{
	memset(head,-1,sizeof(head));
	cin>>n;
	ans=0x7fffffff;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	dfs(1);
	printf("%d\n",ans);//ans存储最大子树节点数的最小值
	return 0;
}

\(4.\)树的直径（树的最长路径）

任取一点\(u\)，从\(u\)点向下向下搜，返回时收集边的权值

\(d1\)记录从\(u\)点往下走的最长路径的长度，\(d2\)记录从\(u\)点往下走的次长路径的长度

\(d[u]=d1+d2\)表示悬挂在\(u\)点上的最长路径的长度

但是，其实不需要开设一个\(d[]\)数组，每遍历完一个点，及时更新全局变量\(ans\)即可，\(ans=max(ans,d1+d2)\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 100010
using namespace std;

int head[maxn],tot;
int vis[maxn];
int ans;

struct Edge
{
	int v,dis,nxt;
	Edge(){}
	Edge(int v,int dis,int nxt):v(v),dis(dis),nxt(nxt){}
}ed[maxn<<1];

void add(int u,int v,int w)
{
	ed[tot]=Edge(v,w,head[u]);
	head[u]=tot++;
}

int dfs(int u)
{
	vis[u]=1;
	int d1=0,d2=0;
	for(int i=head[u];~i;i=ed[i].nxt)
	{
		int son=ed[i].v;
		if(vis[son]) continue;
		int d=dfs(son)+ed[i].dis;
		if(d>=d1) d2=d1,d1=d;
		else if(d>d2) d2=d;
	}
	ans=max(ans,d1+d2);
	return d1;
}

int main()
{
	int n;
	cin>>n;
	memset(head,-1,sizeof(head));
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);add(v,u,w);
	}
	dfs(1);
	printf("%d\n",ans);
	return 0;
}

\(5.\)树的中心

某点到树上其他点的最远距离最近，即为树的中心

从\(u\)点往下走的最长长度：\(d1[u]=d1[v]+w[i]\)，次长长度为\(d2[u]=d2[v]+w[i]\)

从\(u\)点往上走的最长长度，自上而下递推，

如果\(v\)在从\(u\)点向下走的最长路径上，则\(up[v]=w[i]+max(up[u],d2[u])\)

如果\(v\)不在从\(u\)向下走的最长路径上，则\(up[v]=w[i]+max(up[u],d1[u])\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 10010
using namespace std;

int head[maxn],tot;

struct Edge
{
	int v,dis,nxt;
	Edge(){}
	Edge(int v,int dis,int nxt):v(v),dis(dis),nxt(nxt){}
}ed[maxn<<1];

void add(int u,int v,int w)
{
	ed[tot]=Edge(v,w,head[u]);
	head[u]=tot++;
}

int d1[maxn],d2[maxn],up[maxn];
int p1[maxn];//记录从u往下走时的最长路径经过哪个点

int dfs_d(int u,int fa)
{
	d1[u]=0,d2[u]=0;
	for(int i=head[u];~i;i=ed[i].nxt)
	{
		int v=ed[i].v;
		if(v==fa) continue;
		int d=dfs_d(v,u)+ed[i].dis;
		if(d>=d1[u]) d2[u]=d1[u],d1[u]=d,p1[u]=v;
		else if(d>d2[u]) d2[u]=d;
	}
	return d1[u];
}

void dfs_u(int u,int fa)
{
	for(int i=head[u];~i;i=ed[i].nxt)
	{
		int v=ed[i].v;
		if(v==fa) continue;
		if(p1[u]==v) up[v]=ed[i].dis+max(up[u],d2[u]);
		else up[v]=ed[i].dis+max(up[u],d1[u]);
		dfs_u(v,u);
	}
}

int main()
{
	int n;
	memset(head,-1,sizeof(head));
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	dfs_d(1,-1);
	dfs_u(1,-1);
	int res=0x7fffffff;
	for(int i=1;i<=n;i++) res=min(res,max(up[i],d1[i]));
	printf("%d\n",res);
	return 0;
}

\(6.\)积蓄程度

https://www.acwing.com/problem/content/289/

可以利用求树的中心的思想，不必以每个点作源点去做\(dfs\)，而是做两遍\(dfs\)，一次向上，一次向下

从叶向上递推，获取从各点向下流出的最大流量\(d[i]\)，从根向下递推，获取从各点向外流出的最大流量\(f[i]\)（也就是向上加向下的）

向上递推就是先\(dfs\)再计算，向下递推就是先计算再\(dfs\)

\(d[u]=\sum min(w[i],d[v])\),

求外流量用\(u\)更新子结点\(v\)，河道\(u\)与\(v\)这条比的下流量为\(D=min(w[i],d[v])\)，\(u\)点的全流量\(f[u]=D+其他\)(其他包括\(u\)的其他子结点以及\(u\)往上的流量)，\(v\)的上流量\(=min(w[i],f[u]-D)\)

\(v\)点的全流量就为\(f[v]=d[v]+min(w[i],f[u]-D)\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 200010
#define inf 0x7fffffff
using namespace std;

int head[maxn],tot;
int deg[maxn];
int d[maxn],f[maxn];

struct Edge
{
	int v,dis,nxt;
	Edge(){}
	Edge(int v,int dis,int nxt):v(v),dis(dis),nxt(nxt){}
}ed[maxn<<1];

void add(int u,int v,int w)
{
	ed[tot]=Edge(v,w,head[u]);
	head[u]=tot++;
}

int dfs_d(int u,int fa)
{
	for(int i=head[u];~i;i=ed[i].nxt)
	{
		int v=ed[i].v;
		if(v==fa) continue;
		int s=dfs_d(v,u);//返回d[v]
		d[u]+=min(ed[i].dis,s);
	}
	if(deg[u]==1) return inf;//特判叶的情况
	return d[u];
}

void dfs_f(int u,int fa)
{
	for(int i=head[u];~i;i=ed[i].nxt)
	{
		int v=ed[i].v;
		if(v==fa) continue;
		if(deg[u]==1) f[v]=d[v]+ed[i].dis;//特判叶的情况
		else f[v]=d[v]+min(ed[i].dis,f[u]-min(ed[i].dis,d[v]));
		dfs_f(v,u);
	}
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		memset(head,-1,sizeof(head));
		memset(d,0,sizeof(d));
		memset(f,0,sizeof(f));
		memset(deg,0,sizeof(deg));
		for(int i=1;i<n;i++)
		{
			int u,v,w;
			cin>>u>>v>>w;
			add(u,v,w);add(v,u,w);
			deg[u]++;
			deg[v]++;
		}
		dfs_d(1,-1);
		f[1]=d[1];//根只有向下的流量
		dfs_f(1,-1);
		int ans=0;
		for(int i=1;i<=n;i++) ans=max(ans,f[i]);
		printf("%d\n",ans);
	}
	return 0;
}

标签：include,int,d2,dfs,maxn,动态,规划,d1
From： https://www.cnblogs.com/iwillenter-top1/p/17603312.html

相关文章

  • 动态规划四
    复健\(day4\)动态规划（四）状压\(DP\)题目中的要求与位运算相关的表示：\(1.\)同一行不能有相邻的\(1\):\(if(!(i\&(i>>1)))\)\(2.\)某一行不能与上一行的正上方左上方和右上方同时有\(1\)：\(!(a\&b)\)且\(!(a\&b>>1)\)且\(!(a\&b<<1)\)\(3.\)统计\(i\)包含的\(1\)的个数：\(......
  • 情景规划与财务建模2.0，如何促进企业全面预算管理的实施
    近年来，商业世界的不确定因素激增，在此背景下情景规划对于企业发展变得尤为重要。这种技术为企业提供了竞争优势，通过主动寻找增长机会和应对可控风险，构建财务模型来满足企业的稳定发展。这是一种从财务角度保持企业战略目标高效进展、发挥最大价值、拥抱最大回报的方式，往往适用于不同......
  • C/C++ 数据结构五大核心算法之动态规划算法-给你一根长度为 n 的金条，请把金条剪成 m
    动态规划也是一种分治思想，但与分治算法不同的是，分治算法是把原问题分解为若干子问题，自顶向下，求解各子问题，合并子问题的解从而得到原问题的解。动态规划也是自顶向下把原问题分解为若干子问题，不同的是，然后自底向上，先求解最小的子问题，把结果存储在表格中，在求解大的子问题时，直接从表......
  • WPF动态绑定隐藏或显示DataGrid一列
     因为datagridtemplatecolumn不在VirsualTree中，不能继承DataGrid的DataContext，所以想要绑定到datagridtemplatecolumn的visibility，需要添加一个代理 一、添加一個FrameworkElement的代理<Window.Resources><FrameworkElementx:Key="ProxyElement"DataContext......
  • 129.动态编译与静态编译
    129.动态编译与静态编译1.静态编译静态编译是将程序代码和库函数一起编译成一个可执行文件的过程。在静态编译过程中，程序代码和库函数的代码被组合在一起，形成一个独立的可执行文件，该文件可以在任何系统上运行，因为它包含了所有所需的代码和库函数。1.1优点：1.程序在运行时不需要......
  • 恶意代码分析 动态行为分析 Lab3-1 Lab3-2 Lab3-3 Lab3-4
    笔记动态分析基础，这部分还没涉及到看反汇编进行分析，主要是运行程序，然后通过监控软件检测程序运行的内容使用沙箱查看运行报告，可以获取一部分信息首先要在虚拟机上运行恶意代码：如果是DLL，可以通过rundll32.exeDLLName,ExportFun来进行执行如果是服务DLL，则需要运行其中导出的安装服......
  • tp动态匹配多级路径 app/admin/route/app.php
    //请求路径$baseUrl=request()->baseUrl();//访问地址二级目录路由匹配if(substr_count($baseUrl,'/')==3){$baseUrl=substr($baseUrl,1);//动态匹配为二级路由规则Route::rule($baseUrl,substr_replace($baseUrl,'.',strpos($baseUrl,'/',0......
  • 项目散、规划难，建筑行业的税务管理难题该如何解决？
    建筑行业作为我国国民经济的支柱产业之一，发挥着支撑和发展国民经济的重要作用。近年来，建筑业总产值与利润总额增速逐渐放缓，行业产值利润率连续五年下降，利润空间进一步缩小。同时，建筑企业普遍存在债务率高、资金周转偏慢、回收期长等问题，市场进入发展平缓期，粗放式经营已经不适合当下......
  • 面试-基本的算法要了如指掌，比如查找、排序、动态规划、分治等
    在了解这些基本算法之前还是得先了解这些基本的数据结构，这些都是要熟记与心的。基本数据结构比如：字符串、链表、二叉树、堆、栈、队列、哈希等字符串stringstr="helloworld";//使用格式//string是类。//str输出的大小，取决于size函数的返回值。链表classListNode{ pu......
  • 业务架构规划实践：专题一价值链、价值网络和精益价值流分析比较
    引言    本人在四大咨询机构从事制造业数字化咨询工作多年，见证了企业架构方法论的逐步推广和普及，其中以Togaf的4A架构的推广最为成功，被越来越多的企业应用到实际的企业架构的构建当中。而在4A架构中，又以业务架构最为重要，其对上承接企业战略，对下指引应用架构和数据架构的构建......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99