acwing1057. 股票买卖 IV(状态机模型)

acwing1057. 股票买卖 IV(状态机模型)给定一个长度为 N 的数组,数组中的第 i 个数字表示一个给定股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润,你最多可以完成 k 笔交易。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。一次买入卖出合为一笔交易。输入格式第一行包含整数 N 和 k,表示数组的长度以及你可以完成的最大交易数量。第二行包含 N 个不超过 10000 的正整数,表示完整的数组。输出格式输出一个整数,表示最大利润。数据范围1≤N≤105,1≤k≤100输入样例1:3 22

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定一个长度为 N 的数组,数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润,你最多可以完成 k 笔交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。一次买入卖出合为一笔交易。

输入格式
第一行包含整数 N 和 k,表示数组的长度以及你可以完成的最大交易数量。

第二行包含 N 个不超过 10000 的正整数,表示完整的数组。

输出格式
输出一个整数,表示最大利润。

数据范围
1≤N≤105,
1≤k≤100

输入样例1:
3 2
2 4 1
输出样例1:
2
输入样例2:
6 2
3 2 6 5 0 3
输出样例2:
7

样例解释
样例1:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。

样例2:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。共计利润 4+3 = 7.

题解
f[k][i][0]表示第i天已经进行了k次交易并且手里没货的最大收益
f[k][i][1]表示第i天已经进行了k次交易并且手里有货的最大收益

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int KN = 110;
int f[KN][N][2];
int a[N];
const int INF = 0x3f3f3f3f;
int main(){ 
   
    int n,K;
    cin>>n>>K;
    for(int i = 0;i <= K;i ++)f[i][0][1] = -INF;
    for(int i = 1;i <= n;i ++){ 
   
        cin >> a[i];
        for(int k = 0;k <= K;k ++){ 
   
            f[k][i][0] = f[k][i - 1][0];
            if(k >= 1)f[k][i][0] = max(f[k][i][0],f[k - 1][i - 1][1] + a[i]);
            f[k][i][1] = max(f[k][i - 1][1],f[k][i - 1][0] - a[i]);
        }
    }
    cout<<f[K][n][0];
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168862.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • leetcode第一刷_Permutations II

    leetcode第一刷_Permutations II

    2021年12月14日
  • 使用 Python 程序实现摩斯密码翻译器「建议收藏」

    作者主页:海拥作者简介:CSDN全栈领域优质创作者、HDZ核心组成员、蝉联C站周榜前十粉丝福利:往期获奖记录每周送6~9本书,不定期送各种小礼品(搪瓷杯、抱枕、鼠标垫、马克杯等)摩斯密码是一种将文本信息作为一系列通断的音调、灯光或咔嗒声传输的方法,无需特殊设备,熟记的小伙伴即可直接翻译。它以电报发明者SamuelF.B.Morse的名字命名。算法算法非常简单。英语中的每个字符都被一系列“点”和“破折号”代替,或者有时只是单数的“点”或“

  • 海量数据处理:算法

    海量数据处理:算法海量信息即大规模数据,随着互联网技术的发展,互联网上的信息越来越多,如何从海量信息中提取有用信息成为当前互联网技术发展必须面对的问题。在海量数据中提取信息,不同于常规量级数据中提取信息,在海量信息中提取有用数据,会存在以下几个方面的问题:(1)数据量过大,数据中什么情况都可能存在,如果信息数量只有20条,人工可以逐条进行查找、比对,可是当数据规模扩展到上百条、数千条、数亿条,甚至更多时,仅仅只通过手工已经无法解

  • 帝国cms“建立目录不成功,请检查目录权限”的解决方法

    帝国cms“建立目录不成功,请检查目录权限”的解决方法

    2021年11月17日
  • rpm 安装冲突「建议收藏」

    rpm 安装冲突「建议收藏」1.要安装的包比已安装的包旧,则采用降级的方式安装 rpm -Uvhkpartx-0.4.9-72.el6.x86_64.rpm –oldpackage 2.安装的包比已安装的包新,则直接升级即可 rpm -Uvhkpartx-0.4.9-72.el6.x86_64.rpm  或者末尾追加 –replacefiles  或  –repl…

  • 将Map中的key转为驼峰形式输出

    将Map中的key转为驼峰形式输出List<Map<String,Object>>maps=addressDao.selectMaps(wrapper);returnmaps.stream().map(MapUtil::toCamelCaseMap).collect(Collectors.toLis…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号