题解 | 乘之

对于本题，假设k>0，那么对于小龙来讲，就必须尽量选择更多的正数，小蛇则是更多的负数，那么对于原数组a，我们可以将数组a中的数字看作一段一段的连续正数和连续负数的段的排列，假设1 1 -4 -5 1 4，就可以视为 1 1，-4 -5， 1 4，这样的三段，那么对于小龙来讲，他一定会选择第一段的1 1，去扩大新数组的和，那么小蛇就一定会把-4 -5这一段给选择了，这样就会减小新数组的和，但是由于小蛇将相邻的两段正数段中间的负数段给取走了，那么小龙的最优解就会变成从左正段一直取到右正段，将中间的负数段给覆盖，然后小蛇也是这个过程，将中间的正数段给覆盖，直至将整个数组取完

那么我们很容易就能发现，小龙的最优解就是直接将整个数组都给取光，因此本题的最终答案就是数组a中的所有元素相加再乘k

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t;
    cin >> t;
    while (t--) {
        ll n, k;
        cin >> n >> k;
        vector<ll> a(n + 1, (0)), ap;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        ll ans = 0;
        for (int i = 1; i <= n; ++i) ans += (k * a[i]);
        cout << ans << endl;
    }
}