龙星尘 2023-02-26 17:00 采纳率: 42.9%
浏览 48
已结题

C++算法题(动态规划算法)

贝西喜欢看Mooloo的节目。因为贝西是一头忙碌的奶牛,她已经计划了接下来N(1≤N≤10^5)天的时间表,她将观看Mooloo。因为Mooloo是一项付费订阅服务,她现在需要决定如何将需要支付的金额降至最低。

Mooloo有一个有趣的订阅系统:连续d天订阅Mooloo需要d+K(1≤K≤10^9)元钱。您可以随时启动订阅,如果当前订阅到期,您可以根据需要多次启动新订阅。考虑到这一点,计算出贝西为了完成她的计划需要支付的最低金额。

INPUT FORMAT(输入来自终端/stdin):

第一行包含整数N和K。

第二行包含N个整数,描述贝西观看Mooloo的天数:1≤d1<d2<……<dN≤10^14。

OUTPUT FORMAT(输出格式)(将输出打印到终端/标准输出):

请注意,此问题中涉及的大整数大小可能需要使用64位整数数据类型(例如,C/C++中的“long-long”)。

样本输入:

2 4

7 9

样本输出:

7.

贝西在第7天购买了为期三天的订阅,花费d+K=3+4=7元。

样本输入:

2 3

1 10

样本输出:

8.

贝西第一天购买一天的订阅,花费d+K=1+3=4元。贝西还在第10天购买一天的订阅,花费d+K=1+3=4元。贝西总共花了8元。

评分:

输入3-5:N≤10

输入6-12:无额外限制。

这是今天学校布置的题目,我不会,希望各位帮忙解答一下(用C++的算法进行),最希望给出代码和思路!

  • 写回答

3条回答 默认 最新

  • 关注
    
    #include <bits/stdc++.h>
    using namespace std;
    int main() {
        int n, k,cnt=0;
        cin >> n >> k;
        vector<long long> d(n);
        for (int i = 0; i < n; i++) {
            cin >> d[i];
        }
        vector<long long> dp(n + 1, 0);
        for (int i = 1; i <= n; i++) {
    
            if(i>1){
                    cnt+=1;
                dp[i] = min(dp[i-1]+k+1,dp[i-1]+d[cnt]-d[cnt-1]);
            }
    
            else
            dp[i] = dp[i-1]+k+1;
        }
        /*for (int i=1; i <= n; i++) {
           cout<<dp[i]<<endl;
        }*/
        cout << dp[n] << endl;
        return 0;
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 3月7日
  • 已采纳回答 2月27日
  • 创建了问题 2月26日

悬赏问题

  • ¥15 Centos7 / PETGEM
  • ¥15 csmar数据进行spss描述性统计分析
  • ¥15 各位请问平行检验趋势图这样要怎么调整?说标准差差异太大了
  • ¥15 delphi webbrowser组件网页下拉菜单自动选择问题
  • ¥15 wpf界面一直接收PLC给过来的信号,导致UI界面操作起来会卡顿
  • ¥15 init i2c:2 freq:100000[MAIXPY]: find ov2640[MAIXPY]: find ov sensor是main文件哪里有问题吗
  • ¥15 运动想象脑电信号数据集.vhdr
  • ¥15 三因素重复测量数据R语句编写,不存在交互作用
  • ¥15 微信会员卡等级和折扣规则
  • ¥15 微信公众平台自制会员卡可以通过收款码收款码收款进行自动积分吗