StarryCoding-35:鼠鼠我鸭
题目描述
在一个叫做酱西功爷枝叶鸡树学院的地方有𝑛n只小动物，要么是鼠鼠，要么是鸭鸭，从11到𝑛n编号，每只小动物有个体重𝑎𝑖ai。
在这个学校里，存在一种神奇的魔法，可以将编号位于某个区间[𝑙,𝑟][l,r]内的所有鼠鼠都变为鸭鸭，鸭鸭都变为鼠鼠（魔法并不会改变体重）。
现在你可以施放这个魔法至多11次。（也可以不施放）
问最终鸭鸭的总重量最多是多少？
输入格式
第一行一个整数𝑇T表示样例个数。(1≤𝑇≤10)(1≤T≤10)
对于每个样例：
第一行一个整数𝑛n表示小动物的个数。(1≤𝑛≤105)(1≤n≤105)
第二行𝑛n个整数，表示第𝑖i个小动物的类型。00表示鼠鼠，11表示鸭鸭。
第三行𝑛n个整数，表示第𝑖i个小动物的体重𝑎𝑖ai。(1≤𝑎𝑖≤109)(1≤ai≤109)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+9;
ll a[N],w[N];//小动物数组、体重数组
ll prefix[N];//前缀和数组void func(){int n;cin>>n;//输入小动物和体重for(int i = 1; i <= n; ++i) cin >> a[i];for(int i = 1; i <= n; ++i) cin >> w[i];for(int i = 1; i <= n; ++i){if(a[i] == 1){//将鸭鸭的体重变成负的，方便对鼠鼠的体重做前缀和计算prefix[i] = prefix[i-1] + (-1) * w[i];}else{//鼠鼠的体重就是正常的数prefix[i] = prefix[i-1] + w[i];}}ll ess = 0;//ess就是统计施放魔法前的鸭鸭总体重for(int i = 1; i <= n; ++i) ess += a[i] * w[i];ll m = 0, fix = 0;for(int i = 1; i <= n; ++i){//fix是用来记录最大的前缀和，每次都更新//施放魔法后，用fix可以求出到当前的动物为止，最大鸭鸭体重区间的总值fix = max(fix, prefix[i] - m);//m是用来记录当前的前缀和之前的最小的前缀和数值，每次都更新m = min(m, prefix[i]);}cout << ess + fix << '\n';
}int main(){ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);int T;cin >> T;while(T--){func();}return 0;
}