nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

cfedu63D

链接

https://codeforc.es/contest/1155/problem/D

题意

        给你一个长度为n的数组和一个x，现在可以选择至多一段子区间，让这个区间同时乘以x，之后让整个数组的最大子段和最大。

题解

        dp1[i] 前i个数以i结尾最大的连续子串 且不修改 的和 
        dp2[i] 前i个数以i结尾最大的连续子串，且修改区间以i结尾 的和
        dp3[i] 前i个数以i结尾最大的连续子串，且修改区间以1~i结尾 的和