同步于Luogu bolg
题单
T1 AT_arc174_a A Multiply
题意简化
有一个长度为\(n\)的序列\(a\)，你可以选择一个区间，让区间离的数全部\(\times c\)，求\(a\)序列的最大值。
- $ 1\ \le\ N\ \le\ 3\ \times\ 10^5 $
- $ -10^6 \ \le\ C\ \le\ 10^6 $
- $ -10^6 \ \le\ A_i\ \le\ 10^6 $
分析
观察数据范围，可发现\(c\)有正负之分，则想要让序列总长度最大，分类讨论：
- \(c<0\)，则需要使用最小的区间\(\times c\)
- \(c>0\)，则用最大的区间\(\times c\)
- \(c=0\)，则使用最小的区间\(\times c\)
所以要求两个东西：区间最大最小值
发现\(1\le n\le 10^5\)，考虑DP
- 定义状态：\(dp_i \ or \ pd_i\)：以\(i\)结尾的区间最大/最小值
- 答案：\(\max{dp_i}\ or \ \min{pd_i}\)
- 状态转移方程：由于区间是连续的，所以\(dp_i\)的状态只能由\(dp_{i-1}\)得到
对于每个\(dp_i\)：
一.由\(dp_{i-1}+a_i\)，得到新的子段和
二.自己单独成一个子段
得出\(dp_i=\max(dp_{i-1}+a_i,a_i)\)
\(pd\)同理 - 边界条件：\(dp\)设极小值，\(pd\)设极大值
DP值求完了，接下来计算总序列和：
- \((c>0)\)
一.序列不变，因为可能序列全是负数，乘后还变小了
二.减去区间最大值，再加上区间最大值\(\times c\) - \((c\le 0)\)
一.序列不变，因为可能序列全是正数，乘后还变小了
二.减去区间最小值，再加上区间最小值\(\times c\)