前缀和思想的应用——CSP202412B. 梦境巡查

各位好，今天我们来看CSP202412B. 梦境巡查这道题目

归纳一下题意，每到达一个区域需要付出aᵢ的代价，获得bᵢ的收入，发生意外的i处无法获得bᵢ

首先我们先考虑没有意外的情况：

到达1处：w-a₀>0 即w>a₀

到达2处：w-a₀+b₁-a₁>0 即w>a₀+a₁-b₀

到达3处：w-a₀+b₁-a₁+b₂-a₂>0 即w>a₀+a₁+a₂-b₁-b₂

我们不难发现，要想成功到达，w需要大于等于sumA-sumB的最大值

对形如a₀+a₁+a₂-b₁-b₂的式子，我们可以用前缀和进行维护

现在我们再来考虑出现意外的情况，假设第k处出现意外

对0~k-1这一段，结果和之前没有意外时的情况是一样的

而对k后面的任意一处位置x（包括k），通过和刚才一样的推到方式,我们得到如下式子

w>sumA[0~x]-sumB[1~x]+b[k]

由于b[k]是定值，所以实际上w的取值是b[k]+max(sumA[0~x]-sumB[1~x])

因此，我们只需要知道sumA-sumB在k~n这段区间内的最大值即可

我们只需维护一个suffixMax数组，从n往前遍历即可

这样问题就解决了，下面是完整代码：

# include <bits/stdc++.h> using namespace std; #define itn int #define ll long long #define ld long double #define mod 998244353 int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; vector<int> a(n+1); for (int i = 0; i <= n; ++i) cin >> a[i]; vector<int> b(n+1); for (int i = 1; i <= n; ++i) cin >> b[i]; b[0]=0; vector<int> sum(n+1); sum[0] = a[0] - b[0]; for (int i = 1; i <= n; ++i) sum[i] = sum[i-1] + a[i] - b[i]; //维护sumA-sumB vector<int> preMax(n+1); preMax[0] = a[0] ; for (int i = 1; i <= n; ++i) preMax[i] = max(preMax[i-1], sum[i]); //sumA-sumB的最大值 vector<int> sufMax(n+1); sufMax[n] = sum[n]; for (int i = n - 1; i >= 0 ; --i) sufMax[i] = max(sufMax[i+1], sum[i]); vector<int> res(n+1); for (int i = 1;i <= n; ++i) { res[i] = preMax[i-1]; res[i] = max(res[i], sufMax[i] + b[i]); } for (int i = 1;i <= n; ++i) { cout << res[i] << " "; } return 0; }

感谢阅读，欢迎在评论区探讨！

转载请标明出处