各位好今天我们来看CSP202412B. 梦境巡查这道题目归纳一下题意每到达一个区域需要付出aᵢ的代价获得bᵢ的收入发生意外的i处无法获得bᵢ首先我们先考虑没有意外的情况到达1处w-a₀0 即wa₀到达2处w-a₀b₁-a₁0 即wa₀a₁-b₀到达3处w-a₀b₁-a₁b₂-a₂0 即wa₀a₁a₂-b₁-b₂我们不难发现要想成功到达w需要大于等于sumA-sumB的最大值对形如a₀a₁a₂-b₁-b₂的式子我们可以用前缀和进行维护现在我们再来考虑出现意外的情况假设第k处出现意外对0~k-1这一段结果和之前没有意外时的情况是一样的而对k后面的任意一处位置x包括k通过和刚才一样的推到方式,我们得到如下式子wsumA[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; vectorint a(n1); for (int i 0; i n; i) cin a[i]; vectorint b(n1); for (int i 1; i n; i) cin b[i]; b[0]0; vectorint sum(n1); sum[0] a[0] - b[0]; for (int i 1; i n; i) sum[i] sum[i-1] a[i] - b[i]; //维护sumA-sumB vectorint preMax(n1); preMax[0] a[0] ; for (int i 1; i n; i) preMax[i] max(preMax[i-1], sum[i]); //sumA-sumB的最大值 vectorint sufMax(n1); sufMax[n] sum[n]; for (int i n - 1; i 0 ; --i) sufMax[i] max(sufMax[i1], sum[i]); vectorint res(n1); 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; }感谢阅读欢迎在评论区探讨转载请标明出处