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

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

推荐阅读

int
Singleton单例模式和DoubleChecked Locking双重检查锁定模式

问题描述现在，不管开发一个多大的系统（至少我现在的部门是这样的），都会带一个日志功能；在实际开发过程中 ... [详细]

蜡笔小新 2024-11-21 15:14:45
bit
UVALive 8201 - BBP 公式计算圆周率

在1995年，Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后，Bailey 和 Borwein 在他们的论文中发表了这一发现，这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]

蜡笔小新 2024-11-21 18:32:57
int
解决iOS应用推送通知错误：未找到有效aps-environment权限

在尝试加载支持推送通知的iOS应用程序的Ad Hoc构建时，遇到了‘no valid aps-environment entitlement found for application’的错误提示。本文将探讨此错误的原因及多种可能的解决方案。 ... [详细]

蜡笔小新 2024-11-21 19:26:31
bit
二维码的实现与应用

本文介绍了二维码的基本概念、分类及其优缺点，并详细描述了如何使用Java编程语言结合第三方库（如ZXing和qrcode.jar）来实现二维码的生成与解析。 ... [详细]

蜡笔小新 2024-11-21 17:10:15
int
递归实现表达式求和

本文通过C++语言实现了一个递归算法，用于解析并计算数学表达式的值。该算法能够处理加法、减法、乘法和除法操作。 ... [详细]

蜡笔小新 2024-11-21 15:38:13
int
自定义字符串连接函数（避免使用标准库函数）

本文介绍如何手动实现一个字符串连接函数，该函数不依赖于C语言的标准字符串处理函数，如strcpy或strcat。函数原型为void concatenate(char *dest, char *src)，其主要作用是将源字符串src追加到目标字符串dest的末尾。 ... [详细]

蜡笔小新 2024-11-20 17:39:42
int
探讨Java中将图像对象转换为文件和字节数组的方法

本文详细探讨了在Java中如何将图像对象转换为文件和字节数组（Byte[]）的技术。虽然网络上存在大量相关资料，但实际操作时仍需注意细节。本文通过使用JMSL 4.0库中的图表对象作为示例，提供了一种实用的方法。 ... [详细]

蜡笔小新 2024-11-21 21:42:59
int
Linux信号量操作详解：sem_init, sem_wait, sem_post, sem_destroy

本文详细介绍了Linux系统中信号量的相关函数，包括sem_init、sem_wait、sem_post和sem_destroy，解释了它们的功能和使用方法，并提供了示例代码。 ... [详细]

蜡笔小新 2024-11-21 21:21:16
bit
洛谷 P4009 汽车加油行驶问题解析

探讨了经典算法题目——汽车加油行驶问题，通过网络流和费用流的视角，深入解析了该问题的解决方案。本文将详细阐述如何利用最短路径算法解决这一问题，并提供详细的代码实现。 ... [详细]

蜡笔小新 2024-11-21 14:21:38
int
解决SQL Server中几何类型列的INTERSECT操作问题

本文探讨了在SQL Server中处理几何类型列时遇到的INTERSECT操作限制，并提供了解决方案，包括通过转换数据类型和使用额外表结构的方法。 ... [详细]

蜡笔小新 2024-11-20 20:09:58
version
Android与JUnit集成测试实践

本文探讨了如何在Android项目中集成JUnit进行单元测试，并详细介绍了修改AndroidManifest.xml文件以支持测试的方法。 ... [详细]

蜡笔小新 2024-11-20 18:30:14
input
java写简易五子棋游戏。

importjava.io.*;importjava.util.*;publicclass五子棋游戏{staticintm1;staticintn1;staticfinalintS ... [详细]

蜡笔小新 2024-11-20 17:34:54
bit
深入解析WebP图片格式及其应用

随着互联网技术的发展，无论是PC端还是移动端，图片数据流量占据了很大比重。尤其在高分辨率屏幕普及的背景下，如何在保证图片质量的同时减少文件大小，成为了亟待解决的问题。本文将详细介绍Google推出的WebP图片格式，探讨其在实际项目中的应用及优化策略。 ... [详细]

蜡笔小新 2024-11-20 16:31:47
bit
HDU 2028: 扩展最小公倍数问题

本题要求计算一组正整数的最小公倍数（LCM）。输入包括多组测试数据，每组数据首先给出一个正整数n，随后是n个正整数。 ... [详细]

蜡笔小新 2024-11-20 15:52:47
int
linux网络子系统分析（二）—— 协议栈分层框架的建立

目录一、综述二、INET的初始化2.1INET接口注册2.2抽象实体的建立2.3代码细节分析2.3.1socket参数三、其他协议3.1PF_PACKET3.2P ... [详细]

蜡笔小新 2024-11-20 15:21:14

mobiledu2502891023

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

Tags | 热门标签

RankList | 热门文章