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

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

6 人参与  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://zhangshiyu.com/post/32210.html

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

  • 评论(0)
  • 赞助本站

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

最新文章

  • 最新章节_笔趣阁(方黎萧明德)方黎萧明德小说(心跳谋杀论)在线畅读阅读
  • 明月独照成双高分完本(顾明玉齐远修)全书免费_(顾明玉齐远修)明月独照成双高分完本后续(顾明玉齐远修)
  • 真千金的妈,女凭母贵的我内容精选(娇娇顾静怡江稚雅)
  • 雪上春霜在线温观意陆一然完本_雪上春霜在线(温观意陆一然)
  • 男友车祸断腿时,我和新欢在车内拥吻高分言情_陈行简江若***新书_小说后续在线阅读_无删减免费完结_
  • 完结文重生高考填报志愿时,我放任全班上大专好文分享列表_完结文重生高考填报志愿时,我放任全班上大专好文分享(颜禾晚宋津年叶淼淼)
  • 陆寒澈沈秋晚小说完本+外篇(相逢难逃别离)畅享阅读
  • 雪上春霜删减内容修复版本(温观意陆一然)_雪上春霜删减内容修复版本(温观意陆一然)
  • 骤雨淋落晚星(林晚星裴临川)全书浏览_骤雨淋落晚星全书浏览
  • 全书浏览重生高考填报志愿时我放任全班上大专+后续(叶淼淼宋津年颜禾晚)_重生高考填报志愿时我放任全班上大专+后续(叶淼淼宋津年颜禾晚)全书结局
  • 他的甜撩藏不住附加黎初谢时晏:结局+番外免费品鉴(他的甜撩藏不住)全本浏览阅读连载中
  • 全文他死遁后逼疯清冷女权臣+完结+后续(苏煜顾宛柔)列表_全文他死遁后逼疯清冷女权臣+完结+后续

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

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