C/C++，动态 DP 问题的计算方法与源程序

1 文本格式

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 500010;
const int INF = 0x3f3f3f3f;

int Begin[maxn], Next[maxn], To[maxn], e, n, m;
int size[maxn], son[maxn], top[maxn], fa[maxn], dis[maxn], p[maxn], id[maxn], End[maxn];
int cnt, tot, a[maxn], f[maxn][2];

struct matrix {
    int g[2][2];

    matrix() { memset(g, 0, sizeof(g)); }

    matrix operator*(const matrix& b) const  
    {
        matrix c;
        for (int i = 0; i <= 1; i++)
            for (int j = 0; j <= 1; j++)
                for (int k = 0; k <= 1; k++)
                    c.g[i][j] = max(c.g[i][j], g[i][k] + b.g[k][j]);
        return c;
    }
} Tree[maxn], g[maxn]; 

inline void PushUp(int root) {
    Tree[root] = Tree[root << 1] * Tree[root << 1 | 1];
}

inline void Build(int root, int l, int r) {
    if (l == r) {
        Tree[root] = g[id[l]];
        return;
    }
    int Mid = l + r >> 1;
    Build(root << 1, l, Mid);
    Build(root << 1 | 1, Mid + 1, r);
    PushUp(root);
}

inline matrix Query(int root, int l, int r, int L, int R) {
    if (L <= l && r <= R) return Tree[root];
    int Mid = l + r >> 1;
    if (R <= Mid) return Query(root << 1, l, Mid, L, R);
    if (Mid < L) return Query(root << 1 | 1, Mid + 1, r, L, R);
    return Query(root << 1, l, Mid, L, R) *
        Query(root << 1 | 1, Mid + 1, r, L, R);
}

inline void Modify(int root, int l, int r, int pos) {
    if (l == r) {
        Tree[root] = g[id[l]];
        return;
    }
    int Mid = l + r >> 1;
    if (pos <= Mid)
        Modify(root << 1, l, Mid, pos);
    else
        Modify(root << 1 | 1, Mid + 1, r, pos);
    PushUp(root);
}

inline void Update(int x, int val) {
    g[x].g[1][0] += val - a[x];
    a[x] = val;
    while (x) {
        matrix last = Query(1, 1, n, p[top[x]], End[top[x]]);
        Modify(1, 1, n,            p[x]);
        matrix now = Query(1, 1, n, p[top[x]], End[top[x]]);
        x = fa[top[x]];
        g[x].g[0][0] +=
            max(now.g[0][0], now.g[1][0]) - max(last.g[0][0], last.g[1][0]);
        g[x].g[0][1] = g[x].g[0][0];
        g[x].g[1][0] += now.g[0][0] - last.g[0][0];
    }
}

inline void add(int u, int v) {
    To[++e] = v;
    Next[e] = Begin[u];
    Begin[u] = e;
}

inline void DFS1(int u) {
    size[u] = 1;
    int Max = 0;
    f[u][1] = a[u];
    for (int i = Begin[u]; i; i = Next[i]) {
        int v = To[i];
        if (v == fa[u]) continue;
        dis[v] = dis[u] + 1;
        fa[v] = u;
        DFS1(v);
        size[u] += size[v];
        if (size[v] > Max) {
            Max = size[v];
            son[u] = v;
        }
        f[u][1] += f[v][0];
        f[u][0] += max(f[v][0], f[v][1]);
    }
}

inline void DFS2(int u, int t) {
    top[u] = t;
    p[u] = ++cnt;
    id[cnt] = u;
    End[t] = cnt;
    g[u].g[1][0] = a[u];
    g[u].g[1][1] = -INF;
    if (!son[u]) return;
    DFS2(son[u], t);
    for (int i = Begin[u]; i; i = Next[i]) {
        int v = To[i];
        if (v == fa[u] || v == son[u]) continue;
        DFS2(v, v);
        g[u].g[0][0] += max(f[v][0], f[v][1]);
        g[u].g[1][0] += f[v][0];
    }
    g[u].g[0][1] = g[u].g[0][0];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    dis[1] = 1;
    DFS1(1);
    DFS2(1, 1);
    Build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        int x, val;
        scanf("%d%d", &x, &val);
        Update(x, val);
        matrix ans = Query(1, 1, n, 1, End[1]);
        printf("%d\n", max(ans.g[0][0], ans.g[1][0]));
    }
    return 0;
}

2 代码格式

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 500010;
const int INF = 0x3f3f3f3f;

int Begin[maxn], Next[maxn], To[maxn], e, n, m;
int size[maxn], son[maxn], top[maxn], fa[maxn], dis[maxn], p[maxn], id[maxn], End[maxn];
int cnt, tot, a[maxn], f[maxn][2];

struct matrix {
	int g[2][2];

	matrix() { memset(g, 0, sizeof(g)); }

	matrix operator*(const matrix& b) const  
	{
		matrix c;
		for (int i = 0; i <= 1; i++)
			for (int j = 0; j <= 1; j++)
				for (int k = 0; k <= 1; k++)
					c.g[i][j] = max(c.g[i][j], g[i][k] + b.g[k][j]);
		return c;
	}
} Tree[maxn], g[maxn]; 

inline void PushUp(int root) {
	Tree[root] = Tree[root << 1] * Tree[root << 1 | 1];
}

inline void Build(int root, int l, int r) {
	if (l == r) {
		Tree[root] = g[id[l]];
		return;
	}
	int Mid = l + r >> 1;
	Build(root << 1, l, Mid);
	Build(root << 1 | 1, Mid + 1, r);
	PushUp(root);
}

inline matrix Query(int root, int l, int r, int L, int R) {
	if (L <= l && r <= R) return Tree[root];
	int Mid = l + r >> 1;
	if (R <= Mid) return Query(root << 1, l, Mid, L, R);
	if (Mid < L) return Query(root << 1 | 1, Mid + 1, r, L, R);
	return Query(root << 1, l, Mid, L, R) *
		Query(root << 1 | 1, Mid + 1, r, L, R);
}

inline void Modify(int root, int l, int r, int pos) {
	if (l == r) {
		Tree[root] = g[id[l]];
		return;
	}
	int Mid = l + r >> 1;
	if (pos <= Mid)
		Modify(root << 1, l, Mid, pos);
	else
		Modify(root << 1 | 1, Mid + 1, r, pos);
	PushUp(root);
}

inline void Update(int x, int val) {
	g[x].g[1][0] += val - a[x];
	a[x] = val;
	while (x) {
		matrix last = Query(1, 1, n, p[top[x]], End[top[x]]);
		Modify(1, 1, n,			p[x]);
		matrix now = Query(1, 1, n, p[top[x]], End[top[x]]);
		x = fa[top[x]];
		g[x].g[0][0] +=
			max(now.g[0][0], now.g[1][0]) - max(last.g[0][0], last.g[1][0]);
		g[x].g[0][1] = g[x].g[0][0];
		g[x].g[1][0] += now.g[0][0] - last.g[0][0];
	}
}

inline void add(int u, int v) {
	To[++e] = v;
	Next[e] = Begin[u];
	Begin[u] = e;
}

inline void DFS1(int u) {
	size[u] = 1;
	int Max = 0;
	f[u][1] = a[u];
	for (int i = Begin[u]; i; i = Next[i]) {
		int v = To[i];
		if (v == fa[u]) continue;
		dis[v] = dis[u] + 1;
		fa[v] = u;
		DFS1(v);
		size[u] += size[v];
		if (size[v] > Max) {
			Max = size[v];
			son[u] = v;
		}
		f[u][1] += f[v][0];
		f[u][0] += max(f[v][0], f[v][1]);
	}
}

inline void DFS2(int u, int t) {
	top[u] = t;
	p[u] = ++cnt;
	id[cnt] = u;
	End[t] = cnt;
	g[u].g[1][0] = a[u];
	g[u].g[1][1] = -INF;
	if (!son[u]) return;
	DFS2(son[u], t);
	for (int i = Begin[u]; i; i = Next[i]) {
		int v = To[i];
		if (v == fa[u] || v == son[u]) continue;
		DFS2(v, v);
		g[u].g[0][0] += max(f[v][0], f[v][1]);
		g[u].g[1][0] += f[v][0];
	}
	g[u].g[0][1] = g[u].g[0][0];
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n - 1; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	dis[1] = 1;
	DFS1(1);
	DFS2(1, 1);
	Build(1, 1, n);
	for (int i = 1; i <= m; i++) {
		int x, val;
		scanf("%d%d", &x, &val);
		Update(x, val);
		matrix ans = Query(1, 1, n, 1, End[1]);
		printf("%d\n", max(ans.g[0][0], ans.g[1][0]));
	}
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/239171.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

HelpLook VS Confluence：知识管理方面谁更有优势？

HelpLook VS Confluence：知识管理方面谁更有优势？

多年来&#xff0c;在线协作和文档工具市场一直被Confluence所主导。Confluence由Atlassian于2004年创立&#xff0c;很迅速地成为企业寻求强大而全面的协作解决方案和知识管理的热门选择。然而&#xff0c;随着新工具如Notion和HelpLook的出现&#xff0c;市场格局发生了变化&…
阅读更多...
OpenVINS学习3——初始化原理学习

OpenVINS学习3——初始化原理学习

一、OpenVINS初始化概述 VIO初始化的主要意义有&#xff1a; &#xff08;1&#xff09;对齐相机的世界坐标系和惯性系&#xff0c;因此需要估计重力方向。 &#xff08;2&#xff09;为后续的VIO算法提供较为准确的初始参数和状态&#xff08;尺度、IMU bias、初始速度&…
阅读更多...
记录hive/spark取最新且不为null的方法

记录hive/spark取最新且不为null的方法

听标题可能听不懂我想表达的意思&#xff0c;我来描述一下我要做的事&#xff1a; 比如采集同学对某一网站进行数据采集&#xff0c;同一个用户每天会有很多条记录&#xff0c;所以我们要取一条这个用户最新的状态&#xff0c;比如用户改了N次昵称&#xff0c;我们只想得到最后…
阅读更多...
C++STL之List的实现

C++STL之List的实现

首先我们要实现List的STL,我们首先要学会双向带头链表的数据结构。那么第一步肯定是要构建我们的节点的数据结构。 首先要有数据域&#xff0c;前后指针域即可。 再通过模板类进行模板化。 然后再写List的构造函数&#xff0c;这个地方用T&,通过引用就可以减少一次形参拷…
阅读更多...
坑爹的奥数（枚举法）

坑爹的奥数（枚举法）

枚举法是一种解决问题的基本方法&#xff0c;它通过列举问题的所有可能情况来找到问题的解。这种方法适用于问题的解空间相对较小&#xff0c;可以通过穷举所有可能的解来找到最优解或满足特定条件的解。 以下是枚举法的一般步骤&#xff1a; 定义问题&#xff1a; 确定问题的…
阅读更多...
学习-面试java基础-（集合）

学习-面试java基础-（集合）

String 为什么不可变&#xff1f; 1线程安全 2支持hash映射和缓存。因为String的hash值经常会使用到&#xff0c;比如作为 Map 的键&#xff0c;不可变的特性使得 hash 值也不会变&#xff0c;不需要重新计算。 3出于安全考虑。网络地址URL、文件路径path、密码通常情况下都是以…
阅读更多...
易点易动设备管理系统：助力企业高效巡检的智能选择

易点易动设备管理系统：助力企业高效巡检的智能选择

在现代企业管理中&#xff0c;设备巡检是确保设备正常运行和生产高效的重要环节。然而&#xff0c;传统的巡检方式常常面临着效率低下、信息不准确等问题。为了解决这些挑战&#xff0c;易点易动设备管理系统应运而生。本文将详细介绍易点易动设备管理系统如何助力企业实现高效…
阅读更多...
红队攻防实战之DEATHNOTE

红队攻防实战之DEATHNOTE

难道向上攀爬的那条路&#xff0c;不是比站在顶峰更让人热血澎湃吗 渗透过程 获取ip 使用Kali中的arp-scan工具扫描探测 端口扫描 可以看到开放了22和80端口。 访问80端口&#xff0c;重定向到 修改hosts文件&#xff0c;将该域名解析到ip 如图 修改完再次访问&#xff0…
阅读更多...
Python 递归、闭包与装饰器的编程魔法

Python 递归、闭包与装饰器的编程魔法

更多资料获取 &#x1f4da; 个人网站&#xff1a;ipengtao.com 在Python编程中&#xff0c;递归、闭包和装饰器是一些强大的工具&#xff0c;它们能够为代码增色不少&#xff0c;提高代码的可读性和灵活性。本文将深入探讨这三种编程魔法的原理和应用&#xff0c;通过丰富的示…
阅读更多...
040.Python面向对象_设计原则

040.Python面向对象_设计原则

我 的 个 人 主 页&#xff1a;&#x1f449;&#x1f449; 失心疯的个人主页 &#x1f448;&#x1f448; 入 门 教 程 推 荐 &#xff1a;&#x1f449;&#x1f449; Python零基础入门教程合集 &#x1f448;&#x1f448; 虚 拟 环 境 搭 建 &#xff1a;&#x1f449;&…
阅读更多...
【工具栏】idea安装翻译工具

【工具栏】idea安装翻译工具

然后重启idea 打开设置 翻译方式&#xff1a; 选中要翻译的文本 然后右键 运行项目的时候&#xff0c;方便查找错误
阅读更多...
快速幂+高精乘（填坑）洛谷1226+1045

快速幂+高精乘（填坑）洛谷1226+1045

引言 最近在刷题的时候偶然见到这样一个题目&#xff0c;见下图 大致的意思是&#xff0c;让我们计算a的b次方取模p的结果&#xff0c;再我了解了关于快速幂的内容之后&#xff0c;很快便解决了这道题&#xff0c;每次乘完a后取模最后就可以得到结果。但是在这之后&#xff0c…
阅读更多...
淡化了技术指标 还能做现货黄金交易？

淡化了技术指标 还能做现货黄金交易？

技术指标是分析和预测现货黄金走势的其中一种方法&#xff0c;普通投资者多数依赖技术指标为自己的交易做判断。然而&#xff0c;近几年有一种观点认为&#xff0c;我们应该淡化技术指标&#xff0c;少使用或者不用技术分析来服务我们的交易。这个观点引起了不少投资者的思考&a…
阅读更多...
NFTScan | 12.04~12.10 NFT 市场热点汇总

NFTScan | 12.04~12.10 NFT 市场热点汇总

欢迎来到由 NFT 基础设施 NFTScan 出品的 NFT 生态热点事件每周汇总。 周期&#xff1a;2023.12.04~ 2023.12.10 NFT Hot News 01/ NFTScan 与 MintCore 联合推出适用于 NFT 的 Layer2 网络 Mint 12 月 5 日&#xff0c;根据官方消息&#xff0c;NFT 基础设施服务商 NFTScan …
阅读更多...
Ajax跨域请求

Ajax跨域请求

最近使用js构造请求时发生了CORS跨域问题&#xff0c;mark一下 ajax跨域&#xff0c;这应该是最全的解决方案了 | Dailc的个人主页Everything about dailchttps://dailc.github.io/2017/03/22/ajaxCrossDomainSolution.htmlAJAX - 廖雪峰的官方网站研究互联网产品和技术&#…
阅读更多...
基于SSM的乡镇篮球队管理系统论文

基于SSM的乡镇篮球队管理系统论文

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本乡镇篮球队管理系统就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据信…
阅读更多...
华为云CodeArts Artifact：保障制品质量与安全的最佳选择

华为云CodeArts Artifact：保障制品质量与安全的最佳选择

近期&#xff0c;为降低用户使用成本、满足个性化选择诉求&#xff0c;华为云制品仓库CodeArts Artifact 从软件开发生产线 CodeArtS 解耦出来&#xff0c;可单独购买。这是一款打破了传统制品管理的限制&#xff0c;高效、安全、好用的软件包管理工具。 体验通道&#xff1a;…
阅读更多...
独热编码和词向量的简单理解

独热编码和词向量的简单理解

把单词用向量表示&#xff0c;是把深度神经网络语言模型引入自然语言处理领域的一个核心技术。想要让机器理解单词&#xff0c;就必须要把它变成一串数字&#xff08;向量&#xff09;。下面介绍的 One-Hot Encoding&#xff08;One-Hot 编码&#xff09;和 Word Embedding &am…
阅读更多...
接口自动化框架Pytest —— 配置文件pytest.ini的详细使用

接口自动化框架Pytest —— 配置文件pytest.ini的详细使用

前言 我们在执行用例的时候&#xff0c;每次都在命令行中输入-v&#xff0c;-s等一些命令行参数的时&#xff0c;比较麻烦。其中pytest.ini这个配置文件可以快速的帮助我们解决这个问题。 配置文件 pytest.ini文件是pytest的主配置文件&#xff0c;可以改变pytest的运行方式…
阅读更多...
Async 异步任务注解类的用法及原理分析

Async 异步任务注解类的用法及原理分析

背景 看项目源码发现有一个 Async 注解&#xff0c;它是 Spring 的一个注解&#xff0c;作用是在独立的线程中完成注解方法的操作&#xff0c;底层原理是动态代理。 之前不知道这个知识点&#xff0c;小小测试了一下&#xff0c;发现项目中这个注解的用法是错误的&#xff0c…
阅读更多...
最新文章

Copyright @ 2022~2023