股神(dp或贪心)

news/2024/2/27 17:04:29

Description

2020 年 Quasrain 通过炒股赚了一些钱,但是 2021 年又亏了回去。
站在天台上的 Quasrain 开始幻想一个美好世界。
在那个世界 Quasrain 可以预知股票未来 n天的价格,股票每天的涨跌都不会超过 10%。
在第 0 天 Quasrain 拥有一单位金币,股票的价格是一单位金币,
当天 Quasrain 可以选择是否将金币兑换为股票。现在他想知道,n天之后他最多能拥有多少金币。

Input

第一行一个整数 n(1<=n<=500)。
之后一行 n 个小数 a_i,表示之后 n 天每天股票的价格。

Output

输出一行一个小数表示答案,答案保留两位小数。

Sample Input

5
0.92 0.88 0.90 0.93 0.88

Sample Output

1.06

思路:

dp:

由于数据比较小,我们可以用dp,设d【i】为当前能获得最大现金,p[i]为当前能获得最大股票。

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<unordered_map>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1000;
double d[N], p[N], a[N], ma;//d能获得最大现金,p是能获得最大股票
int n;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    a[0] = 1;
    d[0] = 1;
    p[0] = 1;
    ma = d[0];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            p[i] = max(p[i], d[j] / a[i]);
            d[i] = max(d[i], p[j] * a[i]);
        }
        ma = max(d[i], ma);
    }
    printf("%.2f", ma);
    return 0;
}

贪心:

对于a[i]<a[i+1]并且当前拿的是现金,我们买股票可以获得更大现金。

a[i]<a[i+1],拿的是股票,就到下一个点,在这点不卖。

a[i]>a[i+1],拿的是现金,不买。

a[i]>a[i+1],拿的是股票,在这点卖,可以获得当前最大现金。

代码:

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<unordered_map>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1000;
double  x, a[N],f=2;//当前为现金f=-1,若为股票f=1;
int n;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    a[0] = 1;
    x = a[0];
    for (int i = 0; i <= n; i++)
    {
        if (a[i] < a[i + 1] && f !=1)
        {
            x = x / a[i];
            f = 1;

        }
        else if (a[i] > a[i + 1] && f != -1)
        {
            x = x * a[i];
            f = -1;
        }
    }
    printf("%.2f\n", x);
    return 0;
}


http://www.ppmy.cn/news/1170121.html

相关文章

【驱动开发】创建设备节点、ioctl函数的使用

一、控制三盏灯的亮灭 头文件&#xff1a; #ifndef __HEAD_H__ #define __HEAD_H__ typedef struct{unsigned int MODER;unsigned int OTYPER;unsigned int OSPEEDR;unsigned int PUPDR;unsigned int IDR;unsigned int ODR; }gpio_t; #define PHY_LED1_ADDR 0X50006000 #def…

数字孪生智慧建筑可视化系统,提高施工效率和建造质量

随着科技的不断进步和数字化的快速发展&#xff0c;数字孪生成为了建筑行业的一个重要的概念&#xff0c;被广泛应用于智能化建筑的开发与管理中。数字孪生是将现实世界的实体与数字世界的虚拟模型进行连接和同步&#xff0c;从而实现实时的数据交互和模拟仿真。数字孪生在建筑…

‘conda‘ 不是内部或外部命令,也不是可运行的程序 或批处理文件。

原因&#xff1a;环境变量没有正确添加解决&#xff1a;我的电脑—右键属性—高级系统设置—环境变量—系统变量—Path—双击进入—新建&#xff0c;去安装Anaconda的目录下&#xff0c;找到Library中的bin&#xff0c;将此时的路径粘贴到此处

【CSS】CSS 选择器及其优先级

元素选择器&#xff1a;选择特定的HTML元素。优先级较低。 p {/* 样式规则 */ }类选择器&#xff1a;选择具有特定类名的元素。优先级稍高于元素选择器。 .example {/* 样式规则 */ }ID选择器&#xff1a;选择具有特定ID的唯一元素。优先级更高。 #header {/* 样式规则 */ }属性…

Android C/C++ native编程NDK开发中logcat的使用

Android C/C native编程NDK开发中logcat的使用 前言具体用法 前言 在NDK开发过程中&#xff0c;C/C层&#xff0c;需要对代码进行一些调试&#xff0c;日志打印是我们解决异常或崩溃的重要手段&#xff0c;这里我就简单介绍下日志打印三步走。 首先我们先看下官方文档关于日志…

ATX Power Supply

Pinout 20 PIN MOLEX 39-29-9202 at the motherboard 20 PIN MOLEX 39-01-2200 at the cable PinNameColorDescription13.3VOrange+3.3 VDC23.3VOrange+3.3 VDC3COMBlackGround45VRed+5 VDC

Redis | 在Java中操作Redis

在Java中操作Redis&#xff1a; 第一步: pom.xml文件中导入maven依赖第二步: 在application.yml配置文件中 配置Redis数据源第三步: 编写RedisConfiguration配置类&#xff0c;创建RedisTemplate对象第四步: 通过RedisTemplate对象操作Redis / Redis中的数据4.1 操作“字符串St…

聊聊分布式架构07-[Spring]IoC和AOP

目录 Spring IoC IoC的设计与实现 简单容器BeanFactory 高级容器ApplicationContext IoC容器工作过程 Spring AOP 简单的Spring AOP示例 Spring IoC IoC&#xff08;Inversion of Control&#xff09;&#xff1a; IoC是一种设计原则&#xff0c;它反转了传统的控制流。…

Linux 中监控磁盘分区使用情况的 10 个工具

在本文[1]中&#xff0c;我们将回顾一些可用于检查 Linux 中磁盘分区的 Linux 命令行实用程序。 监控存储设备的空间使用情况是系统管理员最重要的任务之一&#xff0c;它可以确保存储设备上有足够的可用空间&#xff0c;以维持 Linux 系统的高效运行。 1. fdisk fdisk 是一个强…

相似度loss汇总,pytorch code

用于约束图像生成&#xff0c;作为loss。 可梯度优化 pytorch structural similarity (SSIM) loss https://github.com/Po-Hsun-Su/pytorch-ssimhttps://github.com/harveyslash/Facial-Similarity-with-Siamese-Networks-in-Pytorch/blob/master/Siamese-networks-medium.ip…

C++类和对象(五) 拷贝构造函数

1 概念 在现实生活中&#xff0c;可能存在一个与你一样的自己&#xff0c;我们称其为双胞胎。那在创建对象时&#xff0c;可否创建一个与已存在对象一某一样的新对象呢&#xff1f; 那在创建对象时&#xff0c;可否创建一个与已存在对象一某一样的新对象呢&#xff1f; 拷贝构造…

系统设计 - 我们如何通俗的理解那些技术的运行原理 - 第五部分:支付系统

本心、输入输出、结果 文章目录 系统设计 - 我们如何通俗的理解那些技术的运行原理 - 第五部分&#xff1a;支付系统前言如何学习支付系统信用卡为什么被称为“银行最赚钱的产品”&#xff1f;VISA/万事达卡如何赚钱&#xff1f;步骤说明为什么开证行应该得到补偿 当我们在商家…

大模型、实时需求推动湖仓平台走向开放

大模型、实时需求高涨 AGI 时代&#xff0c;以 ChatGPT、Midjourney 等为代表的大模型迅速应用加速了 AI 普及&#xff0c;越来越多的企业选择搭建自己的 AI 基础设施&#xff0c;训练行业大模型。 另一方面&#xff0c;企业为了在瞬息万变的市场环境中更快的做出商业决策&…

Android之AMS原理分析

在学习android框架原理过程中&#xff0c;ams的原理非常重要&#xff0c;无论是在面试中还是在自己开发类库过程中都会接触到。 1 简述 ActivityManagerService是Android最核心的服务&#xff0c;负责管理四大组件的启动、切换、调度等工作。由于AMS的功能和重要性&#xff0c…

mybatis plus中json格式实战

1.pom.xml <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/POM/4.0…

YZ系列工具之YZ12:VBA_4种方法设计下拉列表

我给VBA下的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。我的教程一共九套一部VBA手册&#xff0c;教程分为初级、中级、高级三大部分。是对VBA的系统讲解&#xff0c;从简单的…

Ansible的debug模块和魔法变量介绍,fact变量采集和缓存相关操作演示

目录 一.debug模块的使用方法 1.帮助文档给出的示例 2.主要用到的参数 &#xff08;1&#xff09;msg&#xff1a;主要用这个参数来指定要输出的信息 &#xff08;2&#xff09;var&#xff1a;打印指定的变量&#xff0c;一般是通过register注册了的变量 &#xff08;3&…

如何利用示波器解析I2C数据

前言 &#xff08;1&#xff09;如果有嵌入式企业需要招聘校园大使&#xff0c;湖南区域的日常实习&#xff0c;任何区域的暑假Linux驱动实习岗位&#xff0c;可C站直接私聊&#xff0c;或者邮件&#xff1a;zhangyixu02gmail.com&#xff0c;此消息至2025年1月1日前均有效 &am…

2.3.C++项目:网络版五子棋对战之实用工具类模块的设计

文章目录 一、实用工具类模块&#xff08;一&#xff09;功能 二、设计和封装&#xff08;一&#xff09;日志宏封装&#xff08;二&#xff09;mysql_util封装&#xff08;三&#xff09;Jsoncpp-API封装&#xff08;四&#xff09;file_util封装&#xff08;五&#xff09;st…

CUDA编程- __syncthreads()函数

基本概念 __syncthreads() 是CUDA编程中非常关键的一个同步原语。它的功能是确保在某个线程块中的所有线程在执行到这个函数之前都已完成它们之前的所有指令。一旦所有线程都到达这个同步点&#xff0c;它们才可以继续执行__syncthreads()之后的指令。这个函数只能在设备代码&…
最新文章