大家好，我是小码匠，最近开始间歇式滑水，这个节奏我喜欢。。
前置知识
- DP
路漫漫其修远兮，吾将上下而求索
离自己的既定目标：
- 目标：300道
- 已完成：13道
- 待完成：287道
题目描述
官方原题：
- 洛谷：https://www.luogu.com.cn/problem/P9123
贝茜喜欢看 Mooloo 的演出。因为她是一只忙碌的奶牛，她计划在接下来的 N(
) 天去看演出。因为 Mooloo 提供了订阅服务，她想要使她花费的钱最少。
Mooloo 有一个有趣的订阅服务系统：若要在此之后的连续 d 天看演出，则在订阅时需要花费 d K(1≤K≤109) 个单位价格。你可以随时订阅；若本次订阅已经过期，你可以根据需要订阅多次。基于以上条件，请计算出贝茜最少要花费多少个单位价格，才能完成她的计划。
输入格式
第一行输入两个正整数 N 和 K。
第二行输入 N 个正整数，表示在这些天里，贝茜会看 Mooloo 的演出：1≤d_1<d_2<⋯<d_n≤10^{14}
输出格式
请注意，此问题中可能需要使用 64 位整数数据类型（如 C 或 C 中的 long long）。
样例 #1 解释
贝茜在第 7 天时，购买了 3 天的订阅，共花费 d K=3 4=7 个单位价格。
样例 #2 解释
贝茜在第 1 天时，购买了 1 天的订阅，花费 d K=1 3=4 个单位价格；在第 10 天时，也购买了 1 天的订阅，花费 d K=1 3=4 个单位价格。贝茜一共花费了 8 个单位价格。
translated by liyuanchen2021
输入输出样例
输入 #1复制
代码语言：javascript复制2 4
7 9
输出 #1复制
代码语言：javascript复制7
输入 #2复制
代码语言：javascript复制2 3
1 10
输出 #2复制
代码语言：javascript复制8
题解
- https://www.luogu.com.cn/problem/solution/P7859
AC代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
void best_coder() {
int n, k;
cin >> n >> k;
vector<long long> a(n);
vector<long long> dp(n 2);
for (int i = 0; i < n; i) {
cin >> a[i];
}
dp[0] = k 1;
for (int i = 1; i < n; i) {
dp[i] = min (dp[i - 1] k 1, dp[i - 1] a[i] - a[i - 1]);
}
cout << dp[n - 1];
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
参考代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
typedef long long ll;
int main(){
int N, K;
cin >> N >> K;
ll ans = 0LL;
ll day[N];
for(int i = 0; i<N; i ){
cin >> day[i];
if(i == 0){
// It is the first day, I must start a new subscription
ans = K 1LL;
}
else{
// Decide whether to extend a subscription, or end it and start a new one
ll extendCost = day[i] - day[i-1];
ll newCost = K 1LL;
ans = min(extendCost, newCost);
}
}
cout << ans << endl;
}
