首页 > 其他分享 >「BZOJ4899」 记忆的轮廓

「BZOJ4899」 记忆的轮廓

时间:2024-07-28 11:52:34浏览次数:11  
标签:dp3 BZOJ4899 int 存档 701 记忆 轮廓 节点 dp2

题意:从根节点 \(1\) 走到 \(n\),会等概率选择一个儿子走下去,其中 \(1-n\) 的简单路径上编号依次递增,编号在 \([1,n]\) 的叫做正确节点,\([n+1,m]\) 的叫做错误节点,一共有 \(p\) 次存档的机会,\(1\) 和 \(n\) 必须存档,存档只能在正确节点上进行,而且同一个节点不能存多次档,每次到达一个新的正确节点,便可以在这里设立存档点,每当走到一个错误叶子时,就回到当前存档点,最优情况下,期望步数是多少


考虑一个特殊的点 \(p=n\),因为最优,所以一定每个节点都会设立,记 \(d_i\) 为 \(i\) 的儿子节点数量,\(dp3_i\) 表示期望走多少步就会回到存档点 \((n+1\le i \le m)\),\(f_i\) 表示走期望多少步能到达终点 \((1 \le i \le n)\)

那么 \(dp3_i=\frac{\sum dp3_j}{d_i}+1\)(注意特判 \(d_i=0\) 的情况,\(j\) 为 \(i\) 的儿子节点)

\(f_i=\frac{f_{i+1}}{d_i}+\frac{\sum (dp3_j+f_i)}{d_i}+1\),注意因为走错了要回到 \(i\) 重新走,所以是 \(\sum (dp3_j+f_i)\),化简得 \(f_i=f_{i+1}+d_i+\sum dp3_j\) (\(j\) 为 \(i\) 的错误儿子节点)

时间复杂度 \(O(n)\),得分 \(50pts\),注意下面代码把 \(f_i\) 和 \(dp3_i\) 合并写成了 \(dp_i\)

#include<bits/stdc++.h>
using namespace std;
int t,n,m,p,x,y;
double dp[1501];
vector <int> G[1501];
double get(int x){
	if(dp[x]) return dp[x];
	for(int i=0;i<G[x].size();i++){
		get(G[x][i]);
		dp[x]+=dp[G[x][i]];
	}
	if(!G[x].size()) dp[x]=1;
	else dp[x]=1.0*dp[x]/G[x].size()+1;
	return dp[x];
}
int main(){
	scanf("%d",&t);
	while(t--){
		memset(dp,0,sizeof(dp));
		scanf("%d%d%d",&n,&m,&p);
		for(int i=1;i<=m;i++) G[i].clear();
		for(int i=1;i<=m-n;i++){
			scanf("%d%d",&x,&y);
			G[x].push_back(y);
		}
		for(int i=n-1;i>=1;i--){
			for(int j=0;j<G[i].size();j++) dp[i]+=get(G[i][j]);
			dp[i]+=1.0*G[i].size()+dp[i+1]+1;
		}
		printf("%.4lf\n",dp[1]);
	}
	return 0;
}

考虑普通情况,由于我们不知道存档点在哪儿,所以我们只能枚举当前要在哪儿设置与上一次在哪儿设置的,那么记 \(dp1_{i,j}\) 表示从 \(1\) 到 \(j\) 的期望步数,且存了 \(i\) 次档,但我们发现,中间的那些点的贡献又需要枚举来计算,但是时间复杂度无法承受,那么只能预处理出来,记 \(dp2_{i,j}\) 表示只在 \(i\) 设立了存档点,从 \(i\) 到 \(j\) 的期望步数

易得 \(dp1_{i,j}=min(dp1_{i-1,k}+dp2_{k,j})\)

\(dp2_{i,j}=dp2_{i,j-1}+\frac{\sum(dp3_{l}+dp2_{i,j})}{d_{j-1}}+1\),理由和上面的差不多,化简得 \(dp2_{i,j}=d_{j-1} \times dp2_{i,j-1}+\sum dp3_{l}+d_{j-1}\)(\(l\) 为 \(j-1\) 的错误儿子节点)

时间复杂度 \(O(n^2p)\),得分 \(80pts\)(换语言能过)

#include<bits/stdc++.h>
using namespace std;
int t,n,m,p,x,y;
double dp1[701][701],dp2[701][701],dp3[1501];
vector <int> G[1501];
double get(int x){
	if(dp3[x]) return dp3[x];
	for(int i=0;i<G[x].size();i++){
		get(G[x][i]);
		dp3[x]+=dp3[G[x][i]];
	}
	if(!G[x].size()) dp3[x]=1;
	else dp3[x]=1.0*dp3[x]/G[x].size()+1;
	return dp3[x];
}
int main(){
	scanf("%d",&t);
	while(t--){
		memset(dp1,127,sizeof(dp1));
		memset(dp2,0,sizeof(dp2));
		memset(dp3,0,sizeof(dp3));
		scanf("%d%d%d",&n,&m,&p);
		for(int i=1;i<=m;i++) G[i].clear();
		for(int i=1;i<=m-n;i++){
			scanf("%d%d",&x,&y);
			G[x].push_back(y);
		}
		for(int i=1;i<=n;i++){
			dp2[i][i]=0;
			for(int j=i+1;j<=n;j++){
				for(int l=0;l<G[j-1].size();l++) dp2[i][j]+=get(G[j-1][l]);
				dp2[i][j]+=1.0*(dp2[i][j-1]+1)*(G[j-1].size()+1);
			}
		}
		dp1[1][1]=0;
		for(int i=2;i<=p;i++){
			for(int j=2;j<=n;j++){
				for(int k=1;k<j;k++) dp1[i][j]=min(dp1[i][j],dp1[i-1][k]+dp2[k][j]);
			}
		}
		printf("%.4lf\n",dp1[p][n]);
	}
	return 0;
}

发现瓶颈在 \(dp1_{i,j}\) 上,发现它很像基于分治的决策单调性优化形式,打表发现的确满足决策单调性,感性理解 \(dp2_{i,j}\) 单调递增,且增加得越来越快,只能选到恰好合适,也可以二分等方法优化

时间复杂度 \(O(pn\) \(log\) \(n)\),得分 \(100pts\)

#include<bits/stdc++.h>
using namespace std;
int t,n,m,p,x,y;
double dp1[701][701],dp2[701][701],dp3[1501];
vector <int> G[1501];
double get(int x){
	if(dp3[x]) return dp3[x];
	for(int i=0;i<G[x].size();i++){
		get(G[x][i]);
		dp3[x]+=dp3[G[x][i]];
	}
	if(!G[x].size()) dp3[x]=1;
	else dp3[x]=1.0*dp3[x]/G[x].size()+1;
	return dp3[x];
}
void solve(int tim,int L,int R,int ql,int qr){
	if(L>R) return;
	int mid=(L+R)>>1,now=0;
	for(int i=ql;i<=min(mid-1,qr);i++){
		double val=dp1[tim-1][i]+dp2[i][mid];
		if(val<dp1[tim][mid]) dp1[tim][mid]=val,now=i;
	}
	solve(tim,L,mid-1,ql,now);
	solve(tim,mid+1,R,now,qr);
}
int main(){
	scanf("%d",&t);
	while(t--){
		memset(dp1,127,sizeof(dp1));
		memset(dp2,0,sizeof(dp2));
		memset(dp3,0,sizeof(dp3));
		scanf("%d%d%d",&n,&m,&p);
		for(int i=1;i<=m;i++) G[i].clear();
		for(int i=1;i<=m-n;i++){
			scanf("%d%d",&x,&y);
			G[x].push_back(y);
		}
		for(int i=1;i<=n;i++){
			dp2[i][i]=0;
			for(int j=i+1;j<=n;j++){
				for(int l=0;l<G[j-1].size();l++) dp2[i][j]+=get(G[j-1][l]);
				dp2[i][j]+=1.0*(dp2[i][j-1]+1)*(G[j-1].size()+1);
			}
		}
		dp1[1][1]=0;
		for(int i=2;i<=p;i++) solve(i,1,n,1,n);
		printf("%.4lf\n",dp1[p][n]);
	}
	return 0;
}

应该是凸函数吧,那就可以使用 \(\text{wqs}\) 二分继续优化,没有实现了

标签:dp3,BZOJ4899,int,存档,701,记忆,轮廓,节点,dp2
From: https://www.cnblogs.com/zyxawa/p/18328046

相关文章

  • 如何在Python中对轮廓图应用点画?
    我想向XarrayDataArray数据添加点画以指示重要性。该数据是经纬度网格上的二维气候数据。我想提供一个True/False掩码来绘制映射的变量数据。我正在尝试使用contourf来达到此目的,但如果它们更合适,我愿意接受其他方法。我尝试过使用contourf孵化点画重要区域,但......
  • 如何跟踪之前图像的轮廓?
    所以我有一段细菌细胞移动的视频,我将其转换为帧。现在我想找到每个细菌细胞的瞬时速度。为此,我有兴趣了解细菌细胞移动的程度,但我不知道如何告诉我的程序准确识别这种特定细菌的移动。例如,假设我只有两张图像。对于每个图像,我都有每个细菌的COM坐标。现在我如何关联这些数据。......
  • 使用 LangChain 从短暂记忆到持久记忆
    在聊天机器人中构建长期记忆:详细介绍如何将简单的聊天机器人转变为具有长期记忆和上下文理解能力的复杂AI助手   欢迎来到雲闪世界。在聊天机器人中构建长期记忆详细介绍如何将简单的聊天机器人转变为具有长期记忆和上下文理解能力的复杂AI助手   在之......
  • 深入浅出分析最近火热的Mem0个性化AI记忆层
    最近Mem0横空出世,官方称之为PA的记忆层,ThememorylayerforPersonalizedAI,有好事者还称这个是RAG的替代者,Mem0究竟为何物,背后的原理是什么,我们今天来一探究竟。Mem0介绍开源地址:https://github.com/mem0ai/mem0官方介绍为:Mem0providesasmart,self-improvingmemory......
  • 【搜索】【模板】记忆化搜索
    记忆化搜索思想是实现DP的一种手段。优点:不关心递推顺序;对于两维及以上的DP,方便处理初始状态和无效状态。缺点:无法使用滚动数组。注意事项:要什么状态搜什么状态;所有的状态转移都要采取直接搜索的数据很傻。越界的状态不能赋值。实现步骤:先判断是否越界,如果越......
  • 【故障诊断】基于斑马优化算法ZOA优化长短记忆网络LSTM实现故障诊断附matlab代码
    %导入数据集load(‘fault_diagnosis_data.mat’);%假设故障诊断数据保存在fault_diagnosis_data.mat文件中%数据预处理%这里省略了数据预处理的步骤,包括数据归一化、特征提取等%划分训练集和测试集train_ratio=0.8;%训练集占总数据的比例train_size=round......
  • 1.31、基于长短记忆网络(LSTM)的发动机剩余寿命预测(matlab)
    1、基于长短记忆网络(LSTM)的发动机剩余寿命预测的原理及流程基于长短期记忆网络(LSTM)的发动机剩余寿命预测是一种常见的机器学习应用,用于分析和预测发动机或其他设备的剩余可用寿命。下面是LSTM用于发动机剩余寿命预测的原理和流程:数据收集:首先收集发动机的传感器数据,例如......
  • 大模型的短期记忆和上期记忆各自的使用场景
    吾名爱妃,性好静亦好动。好编程,常沉浸于代码之世界,思维纵横,力求逻辑之严密,算法之精妙。亦爱篮球,驰骋球场,尽享挥洒汗水之乐。且喜跑步,尤钟马拉松,长途奔袭,考验耐力与毅力,每有所进,心甚喜之。 吾以为,编程似布阵,算法如谋略,需精心筹谋,方可成就佳作。篮球乃团队之艺,协作共进,方显力......
  • 基于java+ssm+vue记忆旅游-酒店特产商城美食-景点vue(源码+数据库+lw+PPT+讲解视频)
    前言......
  • LangChain让LLM带上记忆
    最近两年,我们见识了“百模大战”,领略到了大型语言模型(LLM)的风采,但它们也存在一个显著的缺陷:没有记忆。在对话中,无法记住上下文的LLM常常会让用户感到困扰。本文探讨如何利用LangChain,快速为LLM添加记忆能力,提升对话体验。LangChain是LLM应用开发领域的最大社区和......