当前位置:首页 » 《随便一记》 » 正文

动态规划之状态机_TGX的博客

3 人参与  2021年12月27日 08:36  分类 : 《随便一记》  评论

点击全文阅读


大盗阿福

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

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

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

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

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

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

数据范围
1≤N≤105,
1≤k≤100
输入样例1:
3 2
2 4 1
输出样例1:
2
题目链接

题解:

1.线性解法

状态定义

dp[i]:为前i家店可以取得的最大收益

状态转移

1.如果抢劫第i家店则dp[i]=dp[i-2]+num[i],因为抢不了第i-1家店所以答案为前i-2家店可获得前加上第i家店的收益
2.如果不抢第i家店则dp[i]=dp[i-1]

二者取个max

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int num[N],dp[N];
int main()
{
    
    int t;
    cin>>t;
    int n;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);
        dp[1]=num[1];
        for(int i=2;i<=n;i++)
        dp[i]=max(dp[i-2]+num[i],dp[i-1]);
             
        cout<<dp[n]<<endl;
    }
}

2.状态机分析
1,dp[i][0]表示不抢劫第i家店可获得的最大金钱
2.dp[i][1]表示抢劫第i家店可获得的最大金钱

如果要偷第 i 家店铺,则第 i-1 店铺不能被偷: dp[i][1]=dp[i-1][0]+num[i];
对于第i天如果不抢有两种方式可以转移到该状态
如果不偷第 i 家店铺,则第 i-1 店铺可以被抢也可以不被抢,取个最大值: dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
const int N=100005,inf=0x3f3f3f3f;
int num[N],dp[N][2];
int main()
{
    
    int t;
    cin>>t;
    int n;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);
       dp[0][1]=-inf;dp[0][0]=0;
       for(int i=1;i<=n;i++)
       {
           dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
           dp[i][1]=dp[i-1][0]+num[i];
       }
       cout<<max(dp[n][0],dp[n][1])<<endl;
    }
}

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/32210.html

家店  数组  可获得  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 京圈佛子破戒后,我改嫁京圈纨绔(沈墨渊,白晶晶)
  • 前世被闺蜜害死,重生后我让她从太子妃变疯女苏婉儿,清歌完本_前世被闺蜜害死,重生后我让她从太子妃变疯女(苏婉儿,清歌)
  • 全书浏览七零军嫂太彪悍,带三宝上军区离婚(沈清落,陈桂花,陆有为)_七零军嫂太彪悍,带三宝上军区离婚(沈清落,陈桂花,陆有为)全书结局
  • 今天也没变成昨天(周扬陈默)全书免费_(周扬陈默)今天也没变成昨天后续(周扬陈默)
  • 重生后,秦总非要父以子贵(许沐晴,秦越泽)全书浏览_重生后,秦总非要父以子贵全书浏览
  • 他嫌弃我喝两块钱豆浆上不了台面,我结婚后他又哭又闹全书万照,白青青在线
  • 昭然若梦前尘烬列表_昭然若梦前尘烬(温昭然方池雲)
  • 导师借我股票账号,我倒欠五十万(孟潇潇,宁薇)_导师借我股票账号,我倒欠五十万孟潇潇,宁薇
  • 拒绝把外卖券给舍友,竹马送我到迪拜捡垃圾(周钰泽,蒋清清,思源)全书浏览_拒绝把外卖券给舍友,竹马送我到迪拜捡垃圾全书浏览
  • 我的人生,你已出局(程森凌古楚文)_我的人生,你已出局程森凌古楚文
  • 穿书成病娇女配,睁眼就签下离婚协议书(朱楼)_穿书成病娇女配,睁眼就签下离婚协议书
  • 老婆逼我给白月光捐肾,我死后她悔疯了(宋逸晨沈墨白)全书浏览_老婆逼我给白月光捐肾,我死后她悔疯了全书浏览

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1