首页 > 其他分享 >abc350E Toward 0

abc350E Toward 0

时间:2024-10-10 22:35:20浏览次数:6  
标签:std double self i64 abc350E auto Toward dp

给定整数N,每次可以选择支付X元将其除以A并向下取整,或者支付Y元掷筛子,假设点数为i,则将其除以i并向下取整,筛子每次都是等概率出现1-6。问将N变成0需要的最小花费的期望。
1<=N<=1E18; 2<=A<=6; 1<=X,Y<=1E9

分析:当前的期望是所有后续情况期望的概率加权。如果选择方案1,概率为1,花费为X;如果选择方案2,6种情况都对应1/6的概率,表示为dp[u] = (dp[u/1]+dp[u/2]+dp[u/3]+dp[u/4]+dp[u/5]+dp[u/6])/6 + Y,移项整理得dp[u]=(dp[u/1]+dp[u/2]+dp[u/3]+dp[u/4]+dp[u/5]+dp[u/6])/5 + 6Y/5,取二者的较小值作为u的最终期望。

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
	i64 N, A, X, Y;
	std::cin >> N >> A >> X >> Y;

	std::map<i64,double> dp;

	auto dfs = [&](auto self, i64 u) -> double {
		if (u == 0) {
			return 0;
		}
		auto it = dp.find(u);
		if (it != dp.end()) {
			return it->second;
		}

		double &res = dp[u];
		double cost1 = X + self(self, u / A);
		double cost2 = 1.2 * Y;
		for (int i = 2; i <= 6; i++) {
			cost2 += 0.2 * self(self, u / i);
		}
		return res = std::min(cost1, cost2);
	};

	std::cout << dfs(dfs, N) << "\n";
}

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cout << std::fixed << std::setprecision(10);
	int t = 1;
	while (t--) solve();
	return 0;
}

标签:std,double,self,i64,abc350E,auto,Toward,dp
From: https://www.cnblogs.com/chenfy27/p/18457331

相关文章

  • General OCR Theory: Towards OCR-2.0 via a Unified End-to-end Model
    摘要传统的OCR系统(OCR-1.0)越来越无法满足人们对智能处理人造光学字符的需求。在本文中,我们将所有人造光学信号(例如,普通文本、数学/分子公式、表格、图表、乐谱,甚至是几何形状)统称为“字符”,并提出了通用OCR理论以及一个优秀的模型,即GOT,以促进OCR-2.0的到来。GOT拥有5.8亿参......
  • SG-SLAM: A Real-Time RGB-D Visual SLAMToward Dynamic Scenes With Semantic andGeo
    目录一、引言二、相关工作A.动态场景中的SLAMB.语义建图三、系统概述A.系统框架B.目标检测C.极线约束D.动态特征剔除策略E.动态特征剔除策略四、实验结果A.基于TUMRGB-D数据集的性能评估B.BonnRGB-D数据集的性能评估 C.动态特征剔除策略的有效性D.时间分析......
  • RestoreFormer++: Towards Real-World Blind Face Restoration from Undegraded Key-V
    RestoreFormer++:TowardsReal-WorldBlindFaceRestorationfromUndegradedKey-ValuePairs(IEEE,2023,8)PaperGitHub动机:认为之前的模型都只关注了图像的纹理信息,而忽视了人脸的细节信息,本文采用多尺度、交叉注意力的方式引入模型的语义信息.总体可以分为两大部分:......
  • Towards Robust Blind Face Restoration with Codebook Lookup Transformer(NeurIPS 2
    TowardsRobustBlindFaceRestorationwithCodebookLookupTransformer(NeurIPS2022)这篇论文试图解决的是盲目面部恢复(blindfacerestoration)问题,这是一个高度不确定的任务,通常需要辅助指导来改善从低质量(LQ)输入到高质量(HQ)输出的映射,或者补充输入中丢失的高质量细节。具体......
  • Towards Achieving Asynchronous MPC with Linear Communication and Optimal Resilie
    Abstract.Securemulti-partycomputation(MPC)allowsasetofnpartiestojointlycomputeafunctionovertheirprivateinputs.TheseminalworksofBen-Or,CanettiandGoldreich[STOC’93]andBen-Or,KelmerandRabin[PODC’94]settledthefeasibility......
  • LogicBench: Towards Systematic Evaluation of Logical Reasoning Ability of Large
    本文是LLM系列文章,针对《LogicBench:TowardsSystematicEvaluationofLogicalReasoningAbilityofLargeLanguageModels》的翻译。LogicBench:大型语言模型逻辑推理能力的系统评价摘要1引言2相关工作3LogicBench4结果和分析5结论局限性摘要最近......
  • Towards Mitigating ChatGPT’s Negative Impact on Education: Optimizing Question
    文章目录题目摘要引言概述实验结果结论和未来工作题目减轻ChatGPT对教育的负面影响:通过布鲁姆分类法优化问题设计论文地址:https://ieeexplore.ieee.org/document/10223662摘要    生成文本AI工具在回答问题方面的流行引发了人们对其可能对学生学业成......
  • attitudes toward coca搭配
    Sorry,therearenomatchingrecords.Youmaywishtodooneofthefollowing:1.Makesurethefrequencylimitsaresetcorrectly(MINFREQandcheckbox)2.Selectalessrestrictivesetofsections(genresortimeperiods)3. Checkthesearchsyntax tow......
  • Unity匀速移动的几种方案 Lerp,SmoothDamp,MoveTowards
    速览Lerp用于插值,可以和协程配合用于移动。SmoothDamp是阻尼移动,从不超过。MoveTowards是匀速移动,也不会超过。 方案1,使用Lerp——先快后慢运动(线性衰减)(不好用✖)Lerp最简单的用法如下:voidUpdate(){transform.position=Vector3.Lerp(transform.position,endPos,Tim......
  • [paper阅读笔记][2023]CorpusLM: Towards a Unified Language Model on Corpusfor Kno
    文章链接:https://arxiv.org/pdf/2402.01176v2Paper的任务处理各种知识密集型任务任务的科学问题本文任务虽然是:提出一个统一的语言模型来处理各种知识密集型任务,但其实其本质科学问题是:如何提高LLMs在知识密集型任务中的检索效率。原因是:LLMs在生成文本时容易出现错误信......