首页 > 其他分享 >Living-Dream 系列笔记 第70期

Living-Dream 系列笔记 第70期

时间:2024-07-31 13:55:05浏览次数:13  
标签:Living 颜色 cur int 一号 70 Dream 节点 dp

登神长阶!

P1272 & P1273

请查阅往期笔记,此处不再赘述。

其中 P1273 我们学到了定义更好求解的状态(一般是转化为价值,如本题),再通过枚举求解最终答案

P8625

容易发现你选出的 \(S\) 一定是一个子树。

然后这题就变成最大子树和了。

关于最大子树和那题,请查阅往期笔记,此处不再赘述。

code
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+5;
int n,a[N];
int dp[N];
vector<int> G[N<<1];

void dfs(int cur,int fa){
	dp[cur]=a[cur];
	for(int i:G[cur]){
		if(i==fa) continue;
		dfs(i,cur);
		dp[cur]=max(dp[cur],dp[cur]+dp[i]);
	}
}

signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1,u,v;i<n;i++)
		cin>>u>>v,
		G[u].push_back(v),
		G[v].push_back(u);
	dfs(1,0);
	//cout<<dp[1]<<'\n';
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
	cout<<ans;
	return 0;
} 

P4362

无与伦比妙妙题。

拿到题目,先抽象出数学模型

则题目可以抽象为:

为树上的所有节点染色,共有 \(m\) 种颜色(钦定一号颜色为大头吃的),

若一条边的两个端点同色,则该边对难受值的贡献即为边权,否则贡献为 \(0\),

其中一号节点必须染一号颜色且必须恰有 \(k\) 个节点染一号颜色,其余颜色必须都染上至少一个节点,

求难受值的最小值,无解输出 \(-1\)。

看到求最值 / 方案数又不要求输出方案的,考虑 dp。

四步法,首先设状态。

从朴素的角度考虑,设一个 \(dp\) 状态使其包含所有要求的信息

即:令 \(dp_{i,j,k}\) 表示以 \(i\) 为根的子树已经选了 \(j\) 个节点染一号颜色且节点 \(i\) 染了 \(k\) 号颜色的难受值的最小值。

定义了状态,我们就先分别考虑空间时间正确性这三方面上是否可行。

空间:\(O(n^3)\),可行。

时间:转移时需要枚举当前节点 \(cur\) 的子树内的 \(j,k\) 以及子节点 \(i\) 与其的子树内的 \(j,k\),大概 \(O(n^5)\),不可行。

正确性:显然可行。

综上,这个状态是不可行的。

但是,容易发现我们只关心一号颜色出现的次数,其他颜色只要出现过就行(即只关心重要部分)。

于是根据这一点,我们可以再次设出一个状态:

令 \(dp_{i,j,0/1}\) 表示以 \(i\) 为根的子树已经选了 \(j\) 个节点染一号颜色且节点 \(i\) 染了 / 没染一号颜色的难受值的最小值。

按照上述三个方面分析一遍,可以得出这个状态是可行的。

接着,我们确定答案。答案显然为 \(dp_{1,k,1}\)。

然后,我们确定初始状态。初始状态显然为 \(dp_{i,0,0}=dp_{i,1,1}=0\)(\(i\) 为树上任意节点)。

推转移方程。显然这是树上背包类的,且需要从 \(0/1\) 两种状态分别转移。

考虑一节点 \(cur\) 及其一子节点 \(i\):

  • 若 \(cur\) 不染一号颜色:

    • 若 \(i\) 染一号颜色,则显然无贡献。

    • 若 \(i\) 不染一号颜色,则除非 \(m=2\),我都可以每层交替放置颜色使得 \(cur \to i\) 这条边无贡献;但若 \(m=2\),则无法交替,于是加上贡献(边权)即可。

  • 若 \(cur\) 染一号颜色:

    • 若 \(i\) 不染一号颜色,则加上贡献。

    • 若 \(i\) 染一号颜色,则显然无贡献。

于是,我们得到状态转移方程:

\[\begin{cases} dp_{cur,j,0}=\min(dp_{cur,j,0},dp_{i,k,1}+dp_{cur,j-k,0},dp_{i,k,0}+dp_{cur,j-k,0}+f \times w)\\ dp_{cur,j,1}=\min(dp_{cur,j,1},dp_{i,k,1}+dp_{cur,j-k,1}+w,dp_{i,k,0}+dp_{cur,j-k,1}) \end{cases} \]

其中 \(w\) 为边权,\(j,k\) 为背包容量、选的物品数,\(f\) 为:

\[\begin{cases} f=1 \ \ \ \ \ \ \text{when}\ m=2\\ f=0 \ \ \ \ \ \ \text{when}\ m\neq2 \end{cases} \]

注意每次转移前 \(dp\) 要重新赋值最大值(因为初始值为 \(0\) 可能影响取 \(\min\),并且以前的答案是阶段答案,不能放到最终答案里去)并备份之前的答案(仍然要参与转移)。

code
#include<bits/stdc++.h>
using namespace std;

const int N=3e2+5;
int n,m,k;
int siz[N],dp[N][N][2],tmp[N][2];
struct E{ int v,w; };
vector<E> G[N<<1];

void dfs(int cur,int fa){
	dp[cur][1][1]=0;
	dp[cur][0][0]=0;
	siz[cur]=1;
	for(auto i:G[cur]){
		if(i.v==fa) continue;
		dfs(i.v,cur);
		siz[cur]+=siz[i.v];
        memcpy(tmp,dp[cur],sizeof tmp);
        memset(dp[cur],0x3f,sizeof dp[cur]);
		for(int j=min(k,siz[cur]);j>=0;j--)
			for(int p=0;p<=min(j,siz[i.v]);p++)
				dp[cur][j][0]=min(dp[cur][j][0],dp[i.v][p][0]+tmp[j-p][0]+(m==2)*i.w),
				dp[cur][j][0]=min(dp[cur][j][0],dp[i.v][p][1]+tmp[j-p][0]),
				dp[cur][j][1]=min(dp[cur][j][1],dp[i.v][p][0]+tmp[j-p][1]),
				dp[cur][j][1]=min(dp[cur][j][1],dp[i.v][p][1]+tmp[j-p][1]+i.w);
	}
}

int main(){
	ios::sync_with_stdio(0);
	memset(dp,0x3f,sizeof dp);
	cin>>n>>m>>k;
	for(int i=1,u,v,w;i<n;i++)
		cin>>u>>v>>w,
		G[u].push_back({v,w}),
		G[v].push_back({u,w});
	if(n-k<m-1) cout<<-1,exit(0);
	dfs(1,0);
	cout<<dp[1][k][1];
	return 0;
}	

标签:Living,颜色,cur,int,一号,70,Dream,节点,dp
From: https://www.cnblogs.com/XOF-0-0/p/18334475

相关文章

  • 代码随想录算法训练营Day0| LeetCode704: 二分查找
    LeetCode704二分查找先看了一下数组理论基础:数组基础题目链接:704.二分查找啥也没看,凭感觉直接上手:classSolution(object): defsearch(self,nums,target): fornuminnums: ifnum==target: returnnums.index(num) break return-1通过倒是......
  • Living-Dream 系列笔记 第69期
    复习树形dp。树形dp定义状态一般套路:令\(dp_i\)表示以\(i\)为子树的xxx(要维护的信息),可以有多维,但一定会有这一维。P2016&P2014请查阅往期笔记,此处不再赘述。P2585以前是分讨每个节点有几个儿子,然后分别转移。其实不用分讨,直接将所有节点视作有两个儿子,初始时将它......
  • springboot校园失物招领系统-计算机毕业设计源码17082
    目 录摘要1绪论1.1研究背景1.2 研究意义1.3论文结构与章节安排2 相关技术介绍2.1B/S结构2.2SpringBoot框架2.3MySQL数据库3系统分析3.1可行性分析3.2系统流程分析3.2.1数据新增流程3.2.2 数据删除流程3.3 系统功能分析3.3.1......
  • Azure 工作项 Azure REST API POST 请求 - 503 服务不可用 0x80070057,无效请求
    我正在尝试使用python脚本以编程方式在Azure板上创建问题卡。我正在使用PAT(个人访问令牌)。headers=base64encodedPATheaders[Content-Type']='application/json-patch+json'payload=dictionary_of_different_values_to_setrequesturl=f"https://dev.azure.co......
  • Sonatype Nexus Repository搭建与使用(详细教程3.70.1)
    目录一.环境准备二.安装jdk三.搭建Nexus存储库四.使用介绍 一.环境准备主机名IP系统软件版本配置信息nexus192.168.226.26Rocky_linux9.4NexusRepository3.70.1MySQL8.0jdk-11.0.232核2G,磁盘20G进行时间同步,关闭防火墙和selinuxJavaArchiveDownloads......
  • Living-Dream 系列笔记 第67期
    树上倍增:维护\(dp_{i,j}\)表示节点\(i\)向上移动\(2^j\)步所到达的节点编号、区间最值、区间和等信息。倍增求LCA:预处理:令\(dp_{i,j}\)表示\(i\)向上走\(2^j\)步所到达的节点。转移:\(dp_{i,j}=dp_{dp_{i,j-1},j-1}\)。初始:\(dp_{i,0}=fa_i\)。查询......
  • 2024世界人工智能大会:智象未来(HiDream.ai)入围多行业示范性应用案例
    在刚刚闭幕的世界人工智能大会(2024WAIC)上,智象未来(HiDream.ai)依托自身领先的行业技术,入围多行业示范性应用案例,充分展示了其在人工智能领域的卓越成就和创新能力。会上,智象未来(HiDream.ai)联合创始人兼CTO姚霆博士正式推出了备受期待的“智象大模型2.0”。新一代多模态大模型......
  • 70%的人都答错了的面试题,vue3的ref是如何实现响应式的?
    前言最近在我的vue源码交流群有位面试官分享了一道他的面试题:vue3的ref是如何实现响应式的?下面有不少小伙伴回答的是Proxy,其实这些小伙伴只回答对了一半。当ref接收的是一个对象时确实是依靠Proxy去实现响应式的。但是ref还可以接收 string、number 或 boolean 这样的......
  • Mocreak Office Installer(Office安装部署工具) v2.3.0.703 中文绿色版
    概述Mocreak是一款一键自动化下载、安装、部署正版Office的办公增强工具。该工具完全免费、无广告、绿色、无毒、简约、高效、安全。软件特点一键快速下载、安装、部署最新版MicrosoftOffice软件。提供简约、高效,且可自定义的图形界面,提升部署效率。支持将Office安装......
  • LeetCode700. 二叉搜索树中的搜索
    题目链接:https://leetcode.cn/problems/search-in-a-binary-search-tree/description/题目叙述:给定二叉搜索树(BST)的根节点root和一个整数值val。你需要在BST中找到节点值等于val的节点。返回以该节点为根的子树。如果节点不存在,则返回null。示例1:输入:root=[1......