『Fwb』冥月凄凉の题解

Pratty · 2025-07-05 13:14:35 · 个人记录

难度：普及/提高-。

思路：思维。

我们很容易想到，Fwb 可以分成以下两种作法：

• 和平作法，不砸场。

  对于这一种做法，我们只需要对每一个摊位判断。如果当前摊位买入后面再卖出可以赚钱，就买，否则就不买。特殊的，第 n 个摊位要留着卖出，因为最后卖出一定最优。

• 暴力作法，砸场。

  首先因为要卖出东西，而砸场后如果不收买不能继续卖出，所以一定要收买。

  由于只能卖出一次东西，而且砸场之后不能再买东西，我们可以证明，砸场一定是连续的，而且只会在连续砸完之后收买一次。因为如果砸场间断，则中间的摊位就少获得了月亮，一定不如连续优。而如果收买很多次，则这些次中间的位置也无法买入月亮，不如全砸了，只收买一次，代价更少，赚的更多。

  我们假设在第 i 个位置砸场，在第 j 个位置收买（i<j）。则在第 i-1 个位置砸场一定要比买入划算。因为买入要付出 v_{i-1} 的代价（v_{i-1}>0），而砸场不需要付出代价（因为一定会在后面收买且仅收买一次）。由此推知，如果要砸场，则一定会从一开始就砸场，即 i=1。

  至于 j 是多少，我们可以循环枚举，统计 a_i 到 a_j 的前缀和，每次计算出赚的冥元数量，最后取最大值，注意要留一个位置收买，一个位置卖出。

代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1100000;
int n, w, ans, sum;
int a[N], v[N], k[N];
signed main() {
    scanf("%lld%lld", &n, &w);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%lld", &v[i]);
    for (int i = 1; i <= n; i++) scanf("%lld", &k[i]);
    for (int i = 1; i < n - 1; i++) {
        sum += a[i];//一直砸到第i个，在第i+1个收买，在i+2及后面任意一个卖出 
        ans = max(ans, sum * w - k[i + 1]);
    }
    sum = 0;
    for (int i = 1; i < n; i++) {//第n个摊位留着卖出月亮 
        sum += max(0LL, w * a[i] - v[i]);//如果买入便宜就取赚的钱，否则取0 
    }
    ans = max(ans, sum);
    printf("%lld", ans);
    return 0;
}