题解：P15906 [TOPC 2024] Business Magic

· · 题解

我们实际上关心的是 r_i 使用的是蓝魔法好还是绿魔法好。

由于绿魔法没有限制，所以我们会有一个“初始价值”sum = \sum |r_i|，然后看看每个 r_i 使用蓝魔法是否会带来更大的贡献（记为 w_i）。

  1. 若 r_i >= 0，使用绿魔法为 r_i，蓝魔法为 2r_i，可以带来 2r_i - r_i = r_i 的贡献。
  2. 若 r_i < 0，使用绿魔法为 -r_i，蓝魔法为 2r_i，可以带来 2r_i - (-r_i) = 3r_i 的贡献。（注意 3r_i < 0。）

我们希望多带来的贡献最大化，且选的 r_i 是连续的，所以求 w_i 的最大子段和（可以是空段，代表不用蓝魔法）就是最大的多带来的贡献。

设 f_i 为以 i 结尾的最大子段和，maxx 为全局的最大子段和：

f_i = \max(f_{i-1},0) + w_i\\maxx = \max(maxx,f_i)

注意若 maxx<0 我们还不如不用蓝魔法好（所以可以直接初始化 maxx \gets 0）。

答案为 sum + maxx。

注意 long long。复杂度 O(n)。

#include<iostream>
#include<utility>
#include<cstdio>
#include<algorithm>
#define re register
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define db double
#define fi const int&
#define fl const ll&
#define ful const ull&
#define fc const char&
#define fs const string&
#define debug() puts("I Love Hina Forever")
using namespace std ;
namespace IO {
    template<class T>inline void read(T &x){char c=getchar(),f=false;x=0;while(c<48||c>57) {f|=(c==45),c=getchar();}while(c>=48&&c<=57){x=(x<<3)+(x<<1)+(c^48),c=getchar();}if(f){x=~x+1;}}
    template<class T,class ...Arg>inline void read(T &x,Arg &...arg){read(x),read(arg...);}
    template<class T>inline void write(T x){if(x<0){putchar(45),x=~x+1;}if(x>9){write(x/10);}putchar(x%10|48);}
    template<class T>inline void write(T x,fc c){write(x),putchar(c);}
}using namespace IO ;
const int N = 3e5 + 5 ;
int n ;
ll f,maxx,ans,sum,a[N] ;
int main () {
    read(n) ;
    for (re int i = 1 ; i <= n ; ++i) read(a[i]) ;
    for (re int i = 1 ; i <= n ; ++i) {
        sum += a[i] >= 0 ? a[i] : -a[i] ;
        a[i] = a[i] >= 0 ? a[i] : 3 * a[i] ;
    }
    for (re int i = 1 ; i <= n ; ++i) f = max(f,0ll) + a[i],maxx = max(maxx,f) ;
    write(sum + maxx) ;
    return 0 ;
}