【第13题】题解及代码分享：滑水模式，我喜欢[USACO23FEB] Watching Mooloo B

小码匠

发布于 2023-11-27 15:24:42

2580

发布于 2023-11-27 15:24:42

文章被收录于专栏：小码匠和老码农

大家好，我是小码匠，最近开始间歇式滑水，这个节奏我喜欢。。

前置知识

路漫漫其修远兮，吾将上下而求索

离自己的既定目标：

目标：300道
已完成：13道
待完成：287道

题目描述

官方原题：

洛谷：https://www.luogu.com.cn/problem/P9123

贝茜喜欢看 Mooloo 的演出。因为她是一只忙碌的奶牛，她计划在接下来的 N(

1≤N≤10^5

) 天去看演出。因为 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复制

2 4
7 9

输出 #1复制

输入 #2复制

2 3
1 10

输出 #2复制

题解

https://www.luogu.com.cn/problem/solution/P7859

AC代码

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

参考代码

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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-11-24，如有侵权请联系 cloudcommunity@tencent.com 删除

int