首页 > 试题广场 >

秘藏

[编程题]秘藏

热度指数：2201 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 1024M，其他语言2048M
算法知识视频讲解

$\hspace{15pt}$ 在这个梦中，世界有表里两面，Askalana初始在表世界，她拾起她脚下的金币，若有所思。

$\hspace{15pt}$ 表、里两个世界各有 $n$ 个点，编号依次为 $1,2,\dots,n$ 。每个点都有一定数量的金币，表世界 $i$ 号点有 $a_i$ 枚金币，里世界 $i$ 号点有 $b_i$ 枚金币。
$\hspace{15pt}$ Askalana初始位于表世界的 $1$ 号点，她拾起该点的金币。之后，她会向当前世界的下一个点移动一步（即，若她当前位于表世界的 $i$ 号点，则她会移动到表世界的 $i + 1$ 号点；若她当前位于里世界的 $i$ 号点，则她会移动到里世界的 $i + 1$ 号点），并拾起该点的金币。
$\hspace{15pt}$ 但Askalana是大魔法师，如果她有不少于 $k$ 枚金币，则她可以选择消耗 $k$ 枚金币，让自己跃迁到对侧世界的 $i + 1$ 号点，并拾起该点的金币。跃迁结束后，如果不再次进行跃迁，她会在对侧世界继续行走下去。
$\hspace{15pt}$ 在最优策略下，Askalana在走到 $n$ 号点时最多可以获得多少金币呢？

输入描述:

第一行输入两个正整数  代表点的数量、跃迁消耗的金币数量。 
第二行输入  个正整数  代表表世界每个点的金币数量。 
第三行输入  个正整数  代表里世界每个点的金币数量。

输出描述:

输出一个正整数，代表Askalana在走到  号点时最多可以获得的金币数量。

示例1

输入

5 3
1 3 1 5 1
2 1 4 1 6

输出

说明

在这个样例中，第  到  个点都在表世界移动，拾起金币  枚。之后，她消耗  枚金币跃迁到里世界，拾起金币  枚。最终，她获得的金币数量为  枚。

算法知识视频讲解

kilomatutinal

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

const ll a=0;

int main() {
    ll n;cin >> n;
    ll k;cin >> k;
    vector<ll> biao(n,0),li(n,0);
    for(ll i=0;i<n;i++) cin >> biao[i];
    for(ll i=0;i<n;i++) cin >> li[i];
    vector<vector<ll>> dp(2,vector<ll>(n+5,0));
    dp[0][0]=biao[0];
    dp[1][0]=-1e9;
    for(ll i=1;i<n;i++)
    {
        dp[0][i]=dp[0][i-1]+biao[i];
        dp[1][i]=dp[1][i-1]+li[i];
        if(dp[0][i-1]>=k)//必须判定，因为不够k时不能穿越
            dp[1][i]=max(dp[1][i],dp[0][i-1]+li[i]-k);
        if(dp[1][i-1]>=k)
            dp[0][i]=max(dp[0][i],dp[1][i-1]+biao[i]-k);
    }
    cout << max(dp[0][n-1],dp[1][n-1]);
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/

发表于 2025-12-24 08:44:17 回复(0)

yousaegg

//@yousaegg
/*  
     /\_/\
    (= ._.)
    / >  \>  这是一只猫猫
    猫猫是不会嫌弃你很菜的
    //此题使用的知识点:动态规划dp
*/
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <string>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <set>
#include <cctype>
#include <cstdio>
using ll =long long;
using lll = __int128_t;
using db = long double;
using namespace std;

const ll MOD_DEFAULT = 998244353;
const ll INF = (ll)2e18 + 10;

namespace FastIO {
    //支持int long long的读取，不支持char和string
    const int BUF_SIZE = 1 << 20;
    char buf[BUF_SIZE], *p1 = buf, *p2 = buf;
    inline char getchar() {
        if (p1 == p2) {
            p1 = buf;
            p2 = buf + fread(buf, 1, BUF_SIZE, stdin);
            if (p1 == p2) return EOF;
        }
        return *p1++;
    }
    template<typename T>
    inline void read(T &x) {
        x = 0;
        char c = getchar();
        bool sign = false;
        while (!std::isdigit(c)) {
            if (c == '-') sign = true;
            c = getchar();
        }
        while (std::isdigit(c)) {
            x = x * 10 + (c - '0');
            c = getchar();
        }
        if (sign) x = -x;
    }
    // 针对整数的特化版本（更快）

    template<>
    inline void read<int>(int &x) {
        x = 0;
        char c = getchar();
        bool sign = false;
        while (c < '0' || c > '9') {
            if (c == '-') sign = true;
            c = getchar();
        }
        while (c >= '0' && c <= '9') {
            x = (x << 1) + (x << 3) + (c ^ 48);
            c = getchar();
        }
        if (sign) x = -x;
    }

    template<>
    inline void read<long long>(long long &x) {
        x = 0;
        char c = getchar();
        bool sign = false;
        while (c < '0' || c > '9') {
            if (c == '-') sign = true;
            c = getchar();
        }
        while (c >= '0' && c <= '9') {
            x = (x << 1) + (x << 3) + (c ^ 48);
            c = getchar();
        }
        if (sign) x = -x;
    }
}
using FastIO::read;

/*##################################################################*/

void solve(){
    int n,k;
    read(n);
    read(k);
    vector<int> a(n+1,0);
    vector<int> b(n+1,0);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    for(int i=1;i<=n;i++){
        read(b[i]);
    }
    vector<vector<ll>> dp(n+1,vector<ll>(2,0));
    //dp[x][y]表示到第x位置，分别在(y=0)表世界和(y=1)里世界的最大金币数量
    dp[1][0]=a[1];
    dp[1][1]=0;
    //cout << dp[1][0] << ' ' << dp[1][1] << '\n';
    for(int i=2;i<=n;i++){
        if(dp[i-1][0]>=k){
            dp[i][1]=b[i]+max(dp[i-1][0]-k,dp[i-1][1]);
        }
        else{
            if(dp[i-1][1]==0){
                dp[i][1]=0;
            }
            else{
                dp[i][1]=b[i]+dp[i-1][1];
            }
        }
        if(dp[i-1][1]>=k){
            dp[i][0]=a[i]+max(dp[i-1][1]-k,dp[i-1][0]);
        }
        else{
            if(dp[i-1][0]==0){
                dp[i][0]=0;
            }
            else{
                dp[i][0]=a[i]+dp[i-1][0];
            }
        }
        //cout << dp[i][0] << ' ' << dp[i][1] << '\n';
    }
    //因为题目保证ai bi都大于0,所以一定能够保证dp[n]的结果是最大的
    cout << max(dp[n][0],dp[n][1]) << '\n';
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int t=1;
    //read(t);
    while(t--){
        solve();
    }
    return 0;
}

发表于 2025-12-24 13:14:44 回复(0)

C++

Reisentyan

我们将使用拉马努金……

注意到，其他题解更加详细，这里就不写了

特别注意！

/*
⡀⠎⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣄⠃⠈⣶⡛⠿⠭⣉⠛⠿⡿⠛⠉⣀⣠⣤⣭⡏⠴⢀⣴⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣷⣱⣬⠛⠉⠀⠀⢠⠀⠀⠀⢀⣀⠀⠉⠿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠈⡿
⠀⠀⠀⠀⠀⠀⠀⢀⢿⣿⣿⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⡏⠀⠀⠀⠀⠈⠳⠀⠀⠀⠻⣿⣿⣿⣿⣿⣿⠋⠀⣇⠀⠀⠀⠀⠀⠀⠀⠀⠈
⠀⠀⠀⠀⠀⠀⠀⣸⠀⣿⣿⣿⣿⠟⠀⠀⠀⠂⠀⠀⢠⠀⠀⠀⠀⠀⠀⠀⠈⡀⠀⠀⠀⠻⣿⣿⣿⣿⣷⡀⠘
⠀⠀⠀⠀⠀⠀⠀⣧⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠙⣿⣿⣿⣿⣿⣄⣧
⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢧⠀⠀⠀⠀⠈⢿⣿⣿⣿⣿⣿⣆
⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⢂⠻⣿⣿⣿⣿⣿⣄
⠀⠀⠀⠀⠀⣿⣿⣿⣿⣹⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣇⠀⠀⠀⠀⠀⡄⠈⢿⣿⣿⣿⣿⣆
⠀⠀⠀⠀⣿⣿⣿⣿⠁⡇⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠀⠀⠀⠐⠸⠀⠀⠻⣿⣿⣿⣆⢦
⠀⠀⢠⣿⣿⣿⣿⠃⠀⠀⠀⠀⠀⠀⠀⣼⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡏⣧⠀⠀⠀⠀⠐⣇⠀⠀⠙⣿⣿⣿⡄⠙⣄
⠀⣴⣿⣿⣿⣿⠏⠀⢸⠀⠀⠀⠀⠀⠀⡿⢿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣃⣈⣦⠀⠀⠀⠀⢹⠀⠀⠀⠸⣿⣿⣿⠀⠀⠳⣀
⠋⣸⣿⣿⣿⡟⠀⠀⠀⡆⠀⠀⠀⠀⠀⡏⠙⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠀⢠⠀⠀⠀⢧⠀⠀⠀⠀⡇⠀⠀⠀⠘⣿⣿⣷⠀⠀⠘
⠀⣿⣿⣿⢩⠀⠀⠀⠀⣿⠀⠀⠀⠀⠀⣀⠀⢱⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠂⢀⣴⣶⣿⣿⡀⠀⠀⢻⠀⠀⠀⠀⠹⣿⣿⡄
⢸⣿⣿⠃⠈⠀⠀⢸⠀⣿⣆⠀⠀⠀⠀⣿⣿⣿⠷⠘⡀⠀⠀⠀⠀⠀⠀⢠⢹⡀⠈⡿⠻⣿⣛⢿⣿⣷⡀⠈⠀⠀⠀⠀⠀⢻⣿⣿
⣿⣿⣿⠀⠀⠀⠀⢸⠀⡇⣼⣄⠀⠀⠀⢻⣿⡄⠑⠑⣿⡀⠀⠀⠀⢀⠀⠂⠇⠀⠀⠖⠛⢿⣿⣿⣌⢿⣿⣿⡆⠀⠀⠀⠀⠀⣿⣿⡀
⣿⣿⡇⠀⠀⠀⠀⢸⠀⣾⣿⣿⡷⠿⣷⣤⣿⣿⡄⠀⠀⠀⠑⠤⡀⠀⠃⠀⠀⠀⠀⣿⣶⣿⣿⣿⣿⣆⠙⣿⣧⠀⠀⠀⠀⠀⣿⣿⡇
⣿⣿⠁⠀⠀⠀⠀⠘⣾⣿⣿⠁⣴⣿⣿⣿⣿⣿⣇⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠸⡏⠙⣿⠉⠻⣿⠀⠀⣿⠀⠀⠀⣄⠀⣿⢸⣷
⣿⣿⡇⠀⠀⠀⠀⠀⣿⣿⠁⠀⣿⣿⠋⣿⠏⠙⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⢀⢻⠀⠀⢀⡟⢀⣿⣸⢃⠟
⣿⣿⣿⠀⡄⠀⠀⠀⠘⠻⡄⠀⢹⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡘⠀⢀⣿⠃⣿⣿⡗⠁
⣧⣿⣿⣧⢹⡀⠀⠀⠀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⣴⣿⣿⣾⣿⣿⣿
⢿⠘⣿⣿⣿⣿⣤⠀⠢⡀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣵⣿⣿⣿⣿⣿⣿⣿⣿⣷
⠀⠉⣿⣿⣿⡿⣿⠻⣷⣬⣓⣬⣄⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠉⠈⠈⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⠃⠼⢉⣿⣿⣿⣿⣿⣿⣿
⠀⠀⣿⣿⣿⣷⠀⠀⠀⠘⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⡏⠀⠀⢸⠀⢻⢿⣿⣿⡏⣿
⠀⢸⣿⣿⣿⣿⠀⠀⠀⠀⢻⣿⣿⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⣾⣿⣿⣿⣿⠀⠀⠀⢸⠀⠀⢸⣿⣿⠘⡀
⢦⡿⣿⣿⣿⢿⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣶⣶⣦⡄⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠘⡄⠀⠈⣿⣿⡄⠱
⣴⠛⣾⣿⣿⢸⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⡄⠀⠀⠀⠀⠀⠀⠀⣯⠛⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⣇⠀⠀⣿⣿⣿
⠿⠀⣿⣿⣿⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⠟⠰⡾⠃⠀⠀⠀⠀⠀⠀⠀⠙⡟⠀⢻⣿⣿⣿⣿⣿⡆⠀⠀⠀⠸⠀⠀⠸⣿⣿⣷
⠆⢳⣿⣿⡇⠀⠀⠀⠀⠀⠀⣿⣿⣿⠛⠿⠿⢿⡟⠀⠀⠉⠦⣀⡤⢶⠀⠖⠲⠶⠊⠀⠀⠀⢻⡛⠛⠛⣿⣿⠀⠀⠀⠀⠃⠀⠀⢿⣿⣿
*/

发表于 2025-12-24 11:08:07 回复(3)

Estrella_pi

牛客周赛88E题。

E-秘藏_牛客周赛 Round 88

发表于 2025-12-24 12:10:59 回复(0)

周康禧

dp一下 dp[i][j]表示到i行j列能得到的最多金币数量，那么i行j列可以从i行j-1列跟i^1行j-1列转移，注意一下转移条件就可以了，最后答案给dp[0][n],dp[1][n]取一下max就行了

void solve(){
    int n,k;
    cin>>n>>k;
    ll c[2][n+1];
    for(int i=1;i<=n;i++){
        cin>>c[0][i];
    }
    for(int i=1;i<=n;i++){
        cin>>c[1][i];
    }
    vector<vector<ll>> dp(2,vector<ll>(n+1,-1e18));
    dp[0][1]=c[0][1];
    for(int i=2;i<=n;i++){
        for(int j=0;j<2;j++){
            if(dp[j^1][i-1]>=k){
                dp[j][i]=max(dp[j^1][i-1]+c[j][i]-k,dp[j][i]);
            }
            dp[j][i]=max(dp[j][i-1]+c[j][i],dp[j][i]);
        }
    }
    cout<<max(dp[1][n],dp[0][n]);
}

发表于 2025-12-24 10:44:30 回复(0)

Python 3

驴主

import sys

data = []
for line in sys.stdin:
    a = list(map(int, line.strip().split()))
    data.append(a)

n, k = data[0]
h, r = data[1:]

dp = [[0] * n for _ in range(2)]
dp[0][0] = h[0]
# 里世界第一位置不可达
dp[1][0] = -114514
for i in range(1, n):
    # 表世界一定可达
    hh, rr = dp[0][i - 1], dp[1][i - 1]
    # 里世界要注意：从不可达状态转移而来 / 金币不够
    dp[0][i] = max(hh, rr - k) + h[i]
    x = max(rr, hh - k)
    dp[1][i] = -114514 if x < 0 else x + r[i]
print(max(dp[0][-1], dp[1][-1]))

# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⠶⠟⠛⠛⠛⠛⠷⡶⠶⠿⠛⠷⠶⣦⣤⡀
# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠶⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠶⣄
# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢶⡀
# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⠫⠒⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢄⠀⠀⠀⠀⠉⢷⡀
# ⠀⠀⠀⠀⠀⠀⣠⡾⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠒⡀⠀⠀⠀⠙⣦
# ⠀⠀⠀⠀⣠⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢆⠀⠀⠀⠘⣧
# ⠀⠀⠀⣴⠁⠀⢀⠤⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢣⠀⠀⠈⢿⡀
# ⠀⠀⡾⠀⣠⢾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡆⠀⠀⠀⠹⣆
# ⠀⢸⢁⠞⠀⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⣿⠀⠀⠀⠀⠀⠀⢰⣿⠑⠢⣄⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠘⣆
# ⠀⠘⠃⠀⠀⡇⠀⠀⠀⠀⠀⠀⠀⠠⠋⢀⢏⢿⠀⠀⠀⠀⠀⢀⣿⣌⣆⠀⠀⣏⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠈⠀⠀⢄⠀⠀⢹⡀
# ⠀⠀⠀⠀⢀⡇⠀⠀⠀⠀⠀⠀⢠⠀⠀⡟⠟⢞⣇⠀⠀⠀⠀⢿⠟⠀⠙⣆⠀⢹⢦⡀⠀⠘⠀⠀⠀⠀⠀⠀⣄⠀⠀⠀⢳⡀⠀⣇
# ⠀⠀⠀⣤⠋⠀⠀⠀⠀⠀⠀⢀⡿⡄⢸⠙⠀⠀⠻⣆⢠⣄⠀⠀⣧⠀⠀⠀⠛⢦⣷⠙⢶⣄⠀⠀⠀⠀⠀⠀⠹⡀⠀⢠⣼⠻⡀⡟
# ⢀⣴⠟⠀⠀⠀⣀⠞⠀⠀⠀⣼⢋⠈⠻⠀⢀⣪⡶⠀⠛⠃⠉⠛⠻⣬⣑⣀⣀⣀⣤⣶⣷⣸⠀⠀⠀⠀⠠⠀⠀⠙⣄⠀⣿⠀⠛
# ⠀⠉⠛⠛⡿⠁⠀⠀⣄⠀⠀⣿⣿⣿⣿⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⣿⣿⣿⡿⠿⡿⠀⠀⠀⠀⠀⡾⠓⠶⠶⠋⠘⣦
# ⠀⠀⢀⠟⠀⠀⠀⣼⣿⣦⡀⠹⡀⠀⠙⠁⠀⠀⠒⠶⠒⠲⠤⠴⠀⠀⠀⠀⠁⠀⠀⠀⣾⠀⠀⠀⠀⠀⡾⠉⢷⣳⢄⠀⠀⠈⠳⣄
# ⠀⠀⡿⠀⠀⠀⣠⣿⣿⢿⣿⠉⠉⠎⢀⠀⡎⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠀⠃⢸⠀⣿⡤⣶⠁⠀⢠⣿⣿⠛⢀⣿⡇⡿⠶⣤⣤⣤⠟
# ⠀⠀⡇⠀⡴⢋⣼⠗⣉⢯⣿⣷⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡾⠀⣀⣾⠉⠉⠀⣠⣿⣿⣧⣿
# ⠀⠀⠹⠟⠀⣧⡴⣻⠃⣾⣿⣿⣋⠛⢶⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣛⣿⣿⣍⣴⣭⣿⡻⣿⣿⣿⣿⣞⣦
# ⠀⠀⠀⠀⠀⣾⣿⠃⢰⣿⠟⠐⣿⢏⣿⣿⣝⣿⣿⣿⠿⠶⠶⠶⠶⠶⠶⣿⠟⣩⠀⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣷⣿⣦⣤
# ⠀⠀⠀⠀⠀⠠⣧⡀⣿⠁⢀⠋⢠⠋⠀⠙⠀⠉⠁⠀⠀⠀⠀⠀⠀⣴⣻⣿⣿⠦⣠⠛⠋⠁⣿⣿⠋⠻⣿⣿⣿⠉⠛⠿⠿⠛⠋
# ⠀⠀⠀⠀⠀⠀⠀⠀⣿⣾⢻⢠⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⢸⣿⡿⣵⠛⠀⠀⠀⠀⠁⠀⠀⠀⣿⠟
# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠻⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣏⡟⡟
# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿

发表于 2025-12-24 17:37:58 回复(1)

patc

题目本身没啥好讲的,送分题,讲讲可能的优化,一个是,本题只需保存两种状态,因此只需要用两个变量记录表世界最优和里世界最优,第二个是第二行输入可以和主循环一起运行,因此第二行不需要塞进单独的数组,用一个变量存就行,这样可以省很多内存空间,不需要用long long 的地方由很多,不开longlong可以节约很多内存和时间

#include <iostream>
using namespace std;
using ll=long long;
int a[200001],b;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    int k;
    cin>>n>>k;
    ll u=0,d=-0x7fffffffffffffff;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b;
        ll nu,nd;
        if(u>=k){
            nd=max(u-k+b,d+b);
        }else{
            nd=d+move(b);
        }
        if(d>=k){
            nu=max(d-k+a[i],move(u)+a[i]);
        }else{
            nu=move(u)+move(a[i]);
        }
        u=move(nu);
        d=move(nd);
    }
    cout<<max(move(u),move(d));//
}
// 64 位输出请用 printf("%lld")

发表于 2025-12-24 15:49:04 回复(0)

提交观点

问题信息

难度：

7条回答 12收藏 109浏览

秘藏

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题