思路：动态规划

以下思路考场能AC，但是有点问题。

定义$dp[i][j][0]$代表$a[i,...,j]$中连续子段的最小值

定义$dp[i][j][1]$代表$a[i,...,j]$中连续子段的最大值

可以采用二维循环求出dp数组。

之后枚举小乖选择哪个子段，然后计算这个子段情况下小坏所能达到的最小贡献，并取最大值即为最终答案。

注意博弈思想，二者均是选择最优的方案，并且是小乖先手。当小乖操作完毕后，无论是什么结果，小坏的最优操作方案均为：

1. $k>0$，选取最小的连续子段和，并将该子段乘$k$
2. $k<0$，选取最大的连续子段和，并将该子段乘$k$

而对于小乖来说，如果在小坏操作完后，其不能达到理想的最大值，那么小乖就应当选择另外一种操作，以达到理想的最大值。

代码

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int length, multiplier;
        length = scanner.nextInt();
        multiplier = scanner.nextInt();

        long[] elements = new long[length + 1];
        long[] prefixSum = new long[length + 1];
        long[][][] dp = new long[length + 1][length + 1][2];

        for (int i = 1; i <= length; i++) {
            elements[i] = scanner.nextLong();
            prefixSum[i] = prefixSum[i - 1] + elements[i];
        }

        for (int segment = 1; segment <= length; segment++) {
            for (int start = 1; start + segment - 1 <= length; start++) {
                int end = start + segment - 1;
                if (segment == 1) {
                    dp[start][end][0] = dp[start][end][1] = elements[start];
                } else {
                    dp[start][end][0] = Math.min(Math.min(dp[start + 1][end][0], dp[start][end - 1][0]), calculateSum(prefixSum, start, end));
                    dp[start][end][1] = Math.max(Math.max(dp[start + 1][end][1], dp[start][end - 1][1]), calculateSum(prefixSum, start, end));
                }
            }
        }

        long maximumValue = Long.MIN_VALUE;
        for (int i = 1; i <= length; i++) {
            for (int j = i; j <= length; j++) {
                long product1 = calculateSum(prefixSum, i, j) * (multiplier - 1);
                long product2 = Math.min(dp[i][j][0] * multiplier * (multiplier - 1), dp[i][j][1] * multiplier * (multiplier - 1));
                if (i != 1) {
                    product2 = Math.min(product2, Math.min(dp[1][i - 1][0] * (multiplier - 1), dp[1][i - 1][1] * (multiplier - 1)));
                }
                if (j != length) {
                    product2 = Math.min(product2, Math.min(dp[j + 1][length][0] * (multiplier - 1), dp[j + 1][length][1] * (multiplier - 1)));
                }
                maximumValue = Math.max(maximumValue, product1 + product2);
            }
        }

        System.out.println(calculateSum(prefixSum, 1, length) + maximumValue);
    }

    private static long calculateSum(long[] prefixSum, int left, int right) {
        return prefixSum[right] - prefixSum[left - 1];
    }
}

思路：线段树维护

比较暴力易想的方法，用线段树维护区间最大最小值。

暴力枚举小乖的操作区间$[l,r]$，然后在线段树上修改并维护。

之后，如果$k>0$，那么小坏需要找到最小子段和，如果$k<0$，那么小坏需要找到最大字段和。而这两个和都维护在线段树的根部了，可以直接获得。

当$k=0$时，答案为0。因为如果最后和大于0，小坏会选所有数字乘0；而如果最后和小于0，那么小乖会选所有数字乘0。

时间复杂度为$O(N^2logN)$

C++

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lson (num<<1)
#define rson (num<<1|1)

const int maxn=1e3+10;
int n;
ll k;
ll a[maxn];

struct node{
	ll lmin,rmin,lmax,rmax,mx,mi,sum;
} tree[maxn<<2];

void build(int l,int r,int num){
	if(l==r){
		tree[num]= (node){a[l],a[l],a[l],a[l],a[l],a[l],a[l]};
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,lson);
	build(mid+1,r,rson);
	tree[num].sum = tree[lson].sum+tree[rson].sum;
	tree[num].mx = max({tree[lson].mx, tree[rson].mx, tree[lson].rmax+tree[rson].lmax});
	tree[num].mi = min({tree[lson].mi, tree[rson].mi, tree[lson].rmin+tree[rson].lmin});
	tree[num].lmax = max({tree[lson].lmax, tree[lson].sum+tree[rson].lmax});
	tree[num].lmin = min({tree[lson].lmin, tree[lson].sum+tree[rson].lmin});
	tree[num].rmax = max({tree[rson].rmax, tree[rson].sum+tree[lson].rmax});
	tree[num].rmin = min({tree[rson].lmin, tree[rson].sum+tree[lson].rmin});
}

void modify(int st,int ed,int l,int r,int num,ll val,bool flag){
	if(st<=l&&ed>=r){
		if(flag){
			tree[num].sum*=k;
			if(k>0){
				tree[num].mx*=k;
				tree[num].mi*=k;
				tree[num].lmax*=k;
				tree[num].lmin*=k;
				tree[num].rmax*=k;
				tree[num].rmin*=k;
			}else{
				ll mi=tree[num].mi, mx=tree[num].mx;
				tree[num].mx=mi*k;
				tree[num].mi=mx*k;
				ll lmax=tree[num].lmax, lmin=tree[num].lmin;
				tree[num].lmax=lmin*k;
				tree[num].lmin=lmax*k;
				ll rmax=tree[num].rmax, rmin=tree[num].rmin;
				tree[num].rmax=rmin*k;
				tree[num].rmin=rmax*k;
			}
			
		}else{
			tree[num].sum/=k;
			if(k>0){
				tree[num].mx/=k;
				tree[num].mi/=k;
				tree[num].lmax/=k;
				tree[num].lmin/=k;
				tree[num].rmax/=k;
				tree[num].rmin/=k;
			}else{
				ll mi=tree[num].mi, mx=tree[num].mx;
				tree[num].mx=mi/k;
				tree[num].mi=mx/k;
				ll lmax=tree[num].lmax, lmin=tree[num].lmin;
				tree[num].lmax=lmin/k;
				tree[num].lmin=lmax/k;
				ll rmax=tree[num].rmax, rmin=tree[num].rmin;
				tree[num].rmax=rmin/k;
				tree[num].rmin=rmax/k;
			}
		}
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=st){
		modify(st,ed,l,mid,lson,val,flag);
	}
	if(mid<ed){
		modify(st,ed,mid+1,r,rson,val,flag);
	}
	tree[num].sum = tree[lson].sum+tree[rson].sum;
	tree[num].mx = max({tree[lson].mx, tree[rson].mx, tree[lson].rmax+tree[rson].lmax});
	tree[num].mi = min({tree[lson].mi, tree[rson].mi, tree[lson].rmin+tree[rson].lmin});
	tree[num].lmax = max({tree[lson].lmax, tree[lson].sum+tree[rson].lmax});
	tree[num].lmin = min({tree[lson].lmin, tree[lson].sum+tree[rson].lmin});
	tree[num].rmax = max({tree[rson].rmax, tree[rson].sum+tree[lson].rmax});
	tree[num].rmin = min({tree[rson].rmin, tree[rson].sum+tree[lson].rmin});
}

int main(){
	std::ios::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	if(k==0){
		cout<<0;
		return 0;
	}
	build(1,n,1);
	ll ans=LLONG_MIN;
	if(k>0){
		for(int len=1;len<=n;++len){
			for(int i=1;i+len-1<=n;++i){
				int j=i+len-1;
				if(i==9&&j==17){
					bool flag=true;
				}
				modify(i,j,1,n,1,k,1);
				ans=max(ans, tree[1].sum + tree[1].mi*(k-1));
				modify(i,j,1,n,1,k,0);
			}
		}
	}else{
		for(int len=1;len<=n;++len){
			for(int i=1;i+len-1<=n;++i){
				int j=i+len-1;
				modify(i,j,1,n,1,k,1);
				ans=max(ans, tree[1].sum + tree[1].mx*(k-1));
				modify(i,j,1,n,1,k,0);
			}
		}
	}
	cout<<ans;
	
	return 0;
}

小乖和小坏在玩一个游戏，游戏中有一个长度为 $n$ 的数组$a_1,a_2,...,a_n$ 和一个固定的整数$k$。游戏规则如下，双方都会执行最优策略:

第一步,小乖选择一个非空的区间 $[l, r]$，将这个区间中的所有数字都乘上 $k$。

第二步, 小坏选择一个非空的区间 $[l, r]$, 将这个区间中的所有数字都乘上 $k$。

记$sum=\sum\limits_{i=1}^n a_i$ 小坏想让$sum$尽可能小，小乖想让$sum$尽可能大，你需要求出最后 $sum$ 的值。

输入描述

第一行输入两个整数 n 和 k$(10^{-5} ≤ k ≤ 10^5, 1 ≤ n ≤ 1000; -10^5 ≤ a_i ≤ 10^5)$,代表数组长度和固定的整数。

第二行输入 $n$ 个整数 $a_1, a_2, ..., a_n$, $(-10^5≤ a_i ≤10^5)$代表数组。

输出描述

在一行上输出一个整数表示答案。

示例 1

输入

6 2
-1 -2 -3 1 2 3

输出

0

说明

小乖会选择区间$[4, 6]$,数组变成{$-1,-2,-3,2,4,6$}；

小坏会选择区间$[1,3]$,数组变成{$-2,-4,-6,2,4,6$}；

数组总和为 $0$。