P15906 [TOPC 2024] Business MagicLink: https://www.luogu.com.cn/problem/P15906题目描述沿街有n nn家商店按从近到远的顺序编号为1 11到n nn。上个月商店k kk的净利润为r k r_krk。如果r k r_krk为正表示盈利r k r_krk美元如果r k r_krk为负表示亏损− r k -r_k−rk美元。作为一名商业魔法大师你拥有两种魔法可以用来改变这些商店下个月的净利润蓝魔法你可以选择一个连续的区间[ L , R ] [L, R][L,R]。该魔法的效果是将从商店L LL到商店R RR包含两端的每家商店的净利润翻倍。也就是说如果k ∈ [ L , R ] k \in [L, R]k∈[L,R]那么商店k kk下个月的净利润为2 r k 2r_k2rk。绿魔法你可以选择任意一家商店对其施放绿魔法。绿魔法的效果是将该商店下个月的净利润变为上个月净利润的相反数。任何未受任何魔法影响的商店其下个月的净利润与上个月相同。然而施放魔法时有一些限制。你只能施放一次蓝魔法且必须在绿魔法之前施放。此外绿魔法不能施放在任何已经受到蓝魔法影响的商店上。你的任务是确定在最优施放魔法后所有商店下个月净利润总和的最大可能值。输入格式第一行包含一个整数n nn表示商店的数量。第二行包含n nn个空格分隔的整数r 1 , r 2 , … , r n r_1, r_2, \dots, r_nr1,r2,…,rn其中r k r_krk是商店k kk上个月的净利润。输出格式输出一个整数表示在最优施放魔法后所有商店下个月净利润总和的最大可能值。输入输出样例 #1输入 #15 -2 5 -3 4 -1输出 #120输入输出样例 #2输入 #27 -1 -1 -1 -1 -1 -1 -1输出 #27输入输出样例 #3输入 #34 998244353 864197532 -7 1000000000输出 #35724883756说明/提示1 ≤ n ≤ 3 × 10 5 1 \le n \le 3 \times 10^51≤n≤3×105− 10 9 ≤ r k ≤ 10 9 -10^9 \le r_k \le 10^9−109≤rk≤109对于k ∈ { 1 , 2 , … , n } k \in \{1, 2, \dots, n\}k∈{1,2,…,n}Solution1. 题意有一个数组蓝魔法可将一段区间内的所有数字加倍绿魔法可将一段区间内所有数字变为相反数。求使用魔法后数组数字总和最大多少。2. 分析本题可算作贪心动态规划的混搭问题。为简明起见我们把初始状态叫做状态 0。贪心部分对状态 0 如果只使用绿魔法那么只要把所有亏损的店变为相反数扭亏为盈即可这种情况下的总利润就是所有数绝对值之和我们把这个已经用绿魔法全部扭亏为盈的状态叫做状态 1。动态规划部分我们考虑在状态 1 的基础上继续推演蓝魔法作用在原本就盈利r k 0 r_k0rk0的店铺产生的额外利润是2 r k − r k r k 2r_k-r_k r_k2rk−rkrk蓝魔法作用在经绿魔法扭亏为盈的店铺r k 0 r_k0rk0由于题目限定蓝魔法不能在绿魔法已经起效的作用下继续使用因此等效结果相当于去掉已有的绿魔法换成蓝魔法产生的贡献是r k − ( − 2 r k ) 3 r k r_k-(-2r_k)3r_krk−(−2rk)3rk注意3 r k 3r_k3rk是一个负值表示的是蓝魔法相比于状态 1 产生的额外亏损。概括起来相交于状态 1蓝魔法对净利润的贡献是盈利盈一倍亏损亏三倍。建立一个在状态 1 的基础上的关于净利润的数组后这个数组显然是有正有负的所求的就是净利润数组的最大子段和。特别注意如果最大子段和为负当且仅当状态 0 下所有的数皆为负数才会出现此种情况那么最大子段和就是空串的最大子段和为零此时最优解就是不使用蓝魔法3. 代码usingSystem;classP15906{staticvoidMain(){intnConvert.ToInt32(Console.ReadLine());// 原始盈利情况long[]rawnewlong[n1];// 蓝魔法贡献通常有正有负long[]contributenewlong[n1];varinputsConsole.ReadLine().Split();for(inti1;in;i){raw[i]Convert.ToInt64(inputs[i-1]);}// 总收入longtotal0;for(inti1;in;i){totalMath.Abs(raw[i]);}// 蓝魔法效果for(inti1;in;i){// 盈利盈一倍,亏损亏三倍contribute[i]raw[i]*(raw[i]0?1:3);}// currentMax: 最大子段和extra: 全局最大子段和longcurrentMax0,extra0;for(inti1;in;i){currentMaxMath.Max(currentMaxcontribute[i],contribute[i]);extraMath.Max(extra,currentMax);}Console.WriteLine(totalextra);}}
