原题链接

思路

设 $s_i$ 表示从 $1$ 到 $i$ 路径的长度。

假设端点序列的第一个点为回路的起点。

对于一个端点，若没有改变方向，那么我们暂时删除它，于是我们得到一个新的端点序列。

设奇数位为左括号，偶数位为右括号，于是总贡献相当于 $\sum_{i=1}^m (-1)^i 2 s_i + a_0$。

设 $f_{i,j,k}$ 表示前 $i$ 个点里有 $j$ 个端点，且共有 $k$ 个左括号为匹配的情况下最大难度。

发现端点一定是括号匹配，且不存在一个前缀使得其能被括号匹配，于是有转移方程：

upd(f[i][j][k], f[i - 1][j][k]); // 不是端点
if (k > 0) upd(f[i][j][k], f[i - 1][j - 1][k]); // 路过
if (k > 1) upd(f[i][j][k], f[i - 1][j - 1][k - 1] + x - s[i] * 2); // 左括号端点
upd(f[i][j][k], f[i - 1][j - 1][k + 1] + x + s[i] * 2); // 右括号端点

注意到题目需要恰好为 $m$，需要考虑路过一个点不转向的情况。

时间复杂度 $O(n^3)$，重点在于将路径问题转化为括号匹配。

另：

好像大部分题解被我hack了：
In

4 4
0 10 -100 10

Out

-160

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 110;
int f[N][N][N];

void upd(int &x, int y) {
    x = (x < y) ? y : x;
}

int main() {
    int n, m, x;
    while (~scanf("%d%d%d", &n, &m, &x)) {
        vector<int> a(n + 10), s(n + 10);
        for (int i = 1; i < n; i ++ ) {
            scanf("%d", &a[i]);
            s[i + 1] = s[i] + a[i];
        }
        memset(f, 0xc0, sizeof f);
        for (int i = 1; i <= n; i ++ ) {
            f[i][0][0] = 0;
            f[i][1][1] = x - s[i] * 2;
            for (int j = 1; j <= i; j ++ ) 
                for (int k = 0; k <= i; k ++ ) {
                    upd(f[i][j][k], f[i - 1][j][k]);
                    if (k > 0) upd(f[i][j][k], f[i - 1][j - 1][k]);
                    if (k > 1) upd(f[i][j][k], f[i - 1][j - 1][k - 1] + x - s[i] * 2);
                    upd(f[i][j][k], f[i - 1][j - 1][k + 1] + x + s[i] * 2);
                }
        }
        printf("%d\n", f[n][m][0]);
    }
    return 0;
}