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

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

推荐阅读

io
【洛谷4251】 [SCOI2015]小凸玩矩阵（二分答案，二分图匹配）

题面传送门Solution看到什么最大值最小肯定二分啊。check直接跑一个二分图匹配就好了。orzztl！！！代码实现*mail:mle ... [详细]

蜡笔小新 2023-10-13 21:37:19
io
Comet OJ - Contest #2 B　她的想法、他的战斗（概率　＋　数学）

题目描述Takuru是一名情报强者，所以他想利用他强大的情报搜集能力来当中间商赚差价。Takuru的计划是让Hinae帮他去市场上买一个商品，然后再以另一个价格卖掉它。Takur ... [详细]

蜡笔小新 2023-10-15 11:48:13
io
【BZOJ1076】【SCOI2008】奖励关（DP、期望、状压）

DescriptionclickmeSolution套路的状压期望DP题。。。考虑倒退期望：设fi,jrolepresentationstyleposi ... [详细]

蜡笔小新 2023-10-15 10:43:49
io
每日算法——并查集的应用

　　并查集是一种群众喜闻乐见的数据结构，其复杂度是数据结构中最奇葩的之一了，Tarjan证明其为阿克曼函数的反函数，在可以想象（不全面的解释啊）的范围内小于等于3。。。我们就把它当做O(1)吧。下面通 ... [详细]

蜡笔小新 2023-10-13 17:27:48
io
Open judge C16H: Magical Balls 快速幂+逆元问题解析

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

蜡笔小新 2023-12-14 12:03:27
io
[CF949D]Curfew 二分答案是个不错的开头，困难部分在于如何检查

本文介绍了一个题目的解法，通过二分答案来解决问题，但困难在于如何进行检查。文章提供了一种逃逸方式，通过移动最慢的宿管来锁门时跑到更居中的位置，从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况，并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后，文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]

蜡笔小新 2023-12-13 09:08:55
io
JZOJ 1266. 玉米田

1266.玉米田(cowfood.pasccpp)(FileIO):input:cowfood.inoutput:cowfood.outTimeLimits:1000msMemor ... [详细]

蜡笔小新 2023-10-14 15:16:32
config
如何自行分析定位SAP BSP错误

The“BSPtag”Imentionedintheblogtitlemeansforexamplethetagchtmlb:configCelleratorbelowwhichi ... [详细]

蜡笔小新 2023-12-14 19:58:05
import
OC学习笔记之@property和@synthesize

本文介绍了OC学习笔记中的@property和@synthesize，包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]

蜡笔小新 2023-12-14 12:05:06
io
《数据结构》学习笔记3——串匹配算法性能评估

本文主要讨论串匹配算法的性能评估，包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库，可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n)，通过随机取出长度为m的子串作为模式P，在文本T中进行匹配，统计平均复杂度。对于成功和失败的匹配分别进行测试，分析其平均复杂度。详情请参考相关学习资源。 ... [详细]

蜡笔小新 2023-12-13 16:16:05
default
高质量SQL书写的30条建议

本文提供了30条关于优化SQL的建议，包括避免使用select *，使用具体字段，以及使用limit 1等。这些建议是基于实际开发经验总结出来的，旨在帮助读者优化SQL查询。 ... [详细]

蜡笔小新 2023-12-13 13:24:33
config
P113：集成日志组件 logback 2彩色日志

第二步，将控制台的日志改成彩色日志，便于查看修改logback.xml文件。 ... [详细]

蜡笔小新 2023-10-14 16:31:17
io
为什么即使Linux服务器的socket关闭，客户端仍能调用一次send函数？

要弄清这个问题，首先需要知道调用send()发送数据时，发生了什么。当调用send()发送数据时，并不是直接将数据发送到网络中，而是先将待发送的数据放到socket发送缓冲区中，然 ... [详细]

蜡笔小新 2023-10-13 16:30:18
function
C语言函数的定义及其含义

本文目录一览：1、C语言函数的特点及其定义?2 ... [详细]

蜡笔小新 2023-10-13 16:14:37
c语言
python视频转字符动画_谁有用python写出来的badapple字符动画

捕获图像，用KMPlayer很容易实现。编码，用了强大的maltab生成3000多张用于播放的字符文本。图像的标号为1（1） ... [详细]

蜡笔小新 2023-10-13 13:50:06

mobiledu2502891023

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

Tags | 热门标签

RankList | 热门文章