今日学习记录
1. https://codeforces.com/contest/2158/problem/C
关键词：贪心 前后缀
问题分析：
给出两个数组 a,b,要正好进行 k 回游戏,对方每次都能进行一次操作,将b[i]加或者减到a[i](同位置的),最后结果为 a 数组中最大的非空子数组和(连续),Alice 要最大化结果,bob 要最小化结果
双方都为最优策略
核心思路:
首先先解决博弈论的普遍问题,真的要进行 k 回合吗?
显然不是,对于 Alice 来说,她选择的是最优的,对 bob 就是最坏的,所以 bob 一定要抵消 Alice 的操作,于是进行 k 次就看是抵消了(k 为偶数),还是 Alice 进行了一次操作(k 为奇数)使 a 数组有最大的非空子数组和
抵消了的情况好说,而且 Alice 可以减或者加,b 可能为负数,所以加 b 的绝对值,所以问题变为
对数组进行一次加a[i]+|b[i]|之后数组的最大非空数组和
前后缀和
这个前后缀和不一样,题目要找的是子数组的最大值,而不是简单的整体数组和,所以要记录每个位置的最大前后缀和,就是看每个位置上的前后最大缀和已经知道,就看每个位置上是加 a 大,还是 b 大
**最终代码：
#include <bits/stdc++.h>
using namespace std;
#define ve vector
using ll = long long;
using ull = unsigned long long;
using sr = string;
using db = double;
const int MOD=998244353;
const ll INF=1e18;
const int DIR[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};
int T;
void solve(){
ll n,k;cin>>n>>k;
ve<ll> a(n),b(n),pre(n),suf(n);
for(int i = 0;i<n;i++) cin>>a[i];
for(int i = 0;i<n;i++) cin>>b[i];
pre[0] = a[0];
for(int i = 1;i<n;i++){
pre[i] = (pre[i-1]>0?pre[i-1]:0LL)+a[i];
}
suf[n-1] = a[n-1];
for(int i = n-2;i>=0;i--){
suf[i] = (suf[i+1]>0?suf[i+1]:0LL)+a[i];
}
k&=1;
ll ans = LLONG_MIN;
if(k==0){
ans = *max_element(pre.begin(),pre.end());
cout<<ans;
}else{
for(int i = 0;i<n;i++){
ans = max(ans,pre[i]+suf[i]-a[i]+abs(b[i]));
}
cout<<ans;
}
cout<<endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>T;
while(T--) solve();
}学到的点： 1.