当前位置: 开发笔记 > 编程语言 > 正文

codeforces710EGenerateaString（dp）

作者：mobiledu2502891023 | 来源：互联网 | 2023-10-11 04:05

题意：给你一个n（1e7），和x，y每次可以1-1*2-花费x，*2花费y问你从0变到n的最小花

题意&＃xff1a;

给你一个n&＃xff08;1e7&＃xff09;&＃xff0c;和x&＃xff0c;y

每次可以&＃43;1/-1/*2

&＃43;-花费x&＃xff0c;*2花费y

问你从0变到n的最小花费

思路&＃xff1a;

关键是n小啊~

对于每个i&＃xff0c;他可能是由i-1加了1

或者i/2乘了2得来的

当前是奇数的时候&＃xff0c;可能是i/2*2&＃43;1或者(i/2&＃43;1)*2-1得来的

前者在i-1加了1里包含了&＃xff0c;所以只需要比较后者

/* ***********************************************
Author :devil
************************************************ */
#include
#include
#include
#include
#include
#include
#include <set>
#include
#include
#include <string>
#include
#include
#define LL long long
#define rep(i,a,b) for(int i&＃61;a;i<&＃61;b;i&＃43;&＃43;)
#define dep(i,a,b) for(int i&＃61;a;i>&＃61;b;i--)
#define ou(a) printf("%d\n",a)
#define pb push_back
#define mkp make_pair
template<class T>inline void rd(T &x)
{char c&＃61;getchar();x&＃61;0;while(!isdigit(c))c&＃61;getchar();while(isdigit(c)){x&＃61;x*10&＃43;c-&＃39;0&＃39;;c&＃61;getchar();}
}
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
using namespace std;
const int inf&＃61;0x3f3f3f3f;
const int mod&＃61;1e9&＃43;7;
const int N&＃61;1e7&＃43;10;
LL dp[N],n,x,y;
int main()
{#ifndef ONLINE_JUDGEIN#endifrd(n),rd(x),rd(y);dp[1]&＃61;x;for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;){dp[i]&＃61;dp[i-1]&＃43;x;if(i&1) dp[i]&＃61;min(dp[i],dp[i/2&＃43;1]&＃43;x&＃43;y);else dp[i]&＃61;min(dp[i],dp[i>>1]&＃43;y);}printf("%I64d\n",dp[n]);return 0;
}

转:https://www.cnblogs.com/d-e-v-i-l/p/5947237.html

推荐阅读

const
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
io
实现下拉列表，点击其他位置自动隐藏效果的三种方式比较

目录实现效果：实现环境实现方法一：基本思路主要代码JavaScript代码总结方法二主要代码总结方法三基本思路主要代码JavaScriptHTML总结实 ... [详细]

蜡笔小新 2023-12-14 15:03:14
const
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新 2023-12-13 19:52:19
const
使用nodejs爬取b站番剧数据，计算最佳追番推荐

本文介绍了如何使用nodejs爬取b站番剧数据，并通过计算得出最佳追番推荐。通过调用相关接口获取番剧数据和评分数据，以及使用相应的算法进行计算。该方法可以帮助用户找到适合自己的番剧进行观看。 ... [详细]

蜡笔小新 2023-12-14 20:44:52
version
解决Docker中volume的权限问题的方法

在Docker中，将主机目录挂载到容器中作为volume使用时，常常会遇到文件权限问题。这是因为容器内外的UID不同所导致的。本文介绍了解决这个问题的方法，包括使用gosu和suexec工具以及在Dockerfile中配置volume的权限。通过这些方法，可以避免在使用Docker时出现无写权限的情况。 ... [详细]

蜡笔小新 2023-12-14 18:48:02
const
在类中定义数组时出错 - Error on defining arrays in class

Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]

蜡笔小新 2023-12-14 17:38:12
char
伊振华作品 | 沈阳市智慧城市运行管理中心的设计与建设

本文介绍了设计师伊振华受邀参与沈阳市智慧城市运行管理中心项目的整体设计，并以数字赋能和创新驱动高质量发展的理念，建设了集成、智慧、高效的一体化城市综合管理平台，促进了城市的数字化转型。该中心被称为当代城市的智能心脏，为沈阳市的智慧城市建设做出了重要贡献。 ... [详细]

蜡笔小新 2023-12-14 16:35:39
const
向QTextEdit拖放文件的方法及实现步骤

本文介绍了在使用QTextEdit时如何实现拖放文件的功能，包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数，并结合QMimeData和QUrl等类，可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]

蜡笔小新 2023-12-14 16:06:38
io
九度OnlineJudge之1002：Grading问题的解决方法

本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程，将每个考题分配给3个独立的专家，如果他们的评分不一致，则需要请一位裁判做出最终决定。文章详细描述了评分规则，并给出了解决该问题的程序。 ... [详细]

蜡笔小新 2023-12-14 13:00:09
const
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
io
推荐系统遇上深度学习(十七）详解推荐系统中的常用评测指标

原创：石晓文小小挖掘机2018-06-18笔者是一个痴迷于挖掘数据中的价值的学习人，希望在平日的工作学习中，挖掘数据的价值， ... [详细]

蜡笔小新 2023-12-13 19:35:25
char
Linux环境变量函数getenv、putenv、setenv和unsetenv详解

本文详细解释了Linux中的环境变量函数getenv、putenv、setenv和unsetenv的用法和功能。通过使用这些函数，可以获取、设置和删除环境变量的值。同时给出了相应的函数原型、参数说明和返回值。通过示例代码演示了如何使用getenv函数获取环境变量的值，并打印出来。 ... [详细]

蜡笔小新 2023-12-13 12:01:03
web
的错误消息：

ZSI.generate.Wsdl2PythonError: unsupported local simpleType restriction ... [详细]

蜡笔小新 2023-12-13 20:28:08
fetch
sklearn数据集库中的常用数据集类型介绍

本文介绍了sklearn数据集库中常用的数据集类型，包括玩具数据集和样本生成器。其中详细介绍了波士顿房价数据集，包含了波士顿506处房屋的13种不同特征以及房屋价格，适用于回归任务。 ... [详细]

蜡笔小新 2023-12-13 17:45:15
fetch
如何通过全新应用内评价获取更多优质用户反馈？

Google Play推出全新的应用内评价API，帮助开发者获取更多优质用户反馈。用户每天在Google Play上发表数百万条评论，这有助于开发者了解用户喜好和改进需求。开发者可以选择在适当的时间请求用户撰写评论，以获得全面而有用的反馈。全新应用内评价功能让用户无需返回应用详情页面即可发表评论，提升用户体验。 ... [详细]

蜡笔小新 2023-12-13 17:23:03

mobiledu2502891023

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章