动态规划

定义 dp[i][0] 和 dp[i][1] 两个状态：

• dp[i][0]：Askalana 到达表世界第 i 号点时，能拥有的最大金币数。
• dp[i][1]：Askalana 到达里世界第 i 号点时，能拥有的最大金币数。

初始化

只有初始状态可达：

• dp[1][0] = a[1]（初始在表世界 1 号点，拾取该点金币）。
• 其余状态（如 dp[1][1]）初始化为 “不可达”。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
#define all(a) a.begin(), a.end()
void init()
{
}
ll dp[200010][2];
void solve()
{
    ll n, k;
    cin >> n >> k;
    memset(dp, -0x3f3f, sizeof(dp));
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
    }
    dp[1][0] = a[1];
    for (int i = 2; i <= n; i++)
    {
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = dp[i - 1][1];
        if (dp[i - 1][1] > k)
            dp[i][0] = max(dp[i][0], dp[i - 1][1] - k);
        if (dp[i - 1][0] > k)
            dp[i][1] = max(dp[i][1], dp[i - 1][0] - k);
        dp[i][1] += b[i];
        dp[i][0] += a[i];
    }
    cout << max(dp[n][1], dp[n][0]) << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int qwq = 1;
    // cin >> qwq;
    while (qwq--)
    {
        solve();
    }
    return 0;
}