C++算法题（动态规划算法）

Question

贝西喜欢看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++的算法进行），最希望给出代码和思路！

Answer 1

#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;
}