「AtCoder ABC128-D」equeue

Description

给定一个长度为 $n$ 的序列 $\{v\}$，你最多可以进行 $m$ 次操作，操作有 $4$ 种：

把最左端的数放在手里；
把最右端的数放在手里；
把手中的某个数放回序列最左端；
把手中的某个数放回序列最右端。

求手中数的总和最大是多少。$(1 \leq n \leq 50,1 \leq m \leq 100,-10^7 \leq v_i \leq 10^7)$

Source

[AtCoder]ABC128-D

Solution

显然答案一定是先从左边取若干数，放回取走的若干数；再从右边取若干数，放回取走的若干数。取和放的操作总数不超过 $m$ 。

尝试 动态规划 。

我们用 $f_{i,j}$ 表示取前 $i$ 个数，其中放回 $j$ 个数的最大价值，$g_{i,j}$ 表示取末尾 $i$ 个数，其中放回 $j$ 个数的最大价值。

其实只要会求 $f$，翻转数组求能用同样的方法求 $g$ 了。

对于 $f_{i,j}$，考虑第 $i$ 个数选还是不选。

如果选，取前 $i - 1$ 个数放回 $j$ 个数的最大价值为 $f_{i-1,j}$，还要加上 $v_i$ 。

如果不选，那么只能取前 $i - 1$ 个数并放回 $j - 1$ 个数，最大价值为 $f_{i-1,j-1}$ 。

取上述两个值的较大值即可。

即

$\large { f_{i,j} = \max\left(f_{i-1,j-1}, f_{i - 1,j} + v_i \right) }$

最后通过 $f$ 和 $g$ 合并答案即可，注意 $m$ 次操作不一定要用完。$\rm DP$ 时间复杂度为 $O(nm)$，合并复杂度为 $O(n^2m^2)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 100;
const LL INF = 0x7fffffffffffffff;
int n, m;
LL ans, v[MAXN + 5], f[MAXN + 5][MAXN + 5], g[MAXN + 5][MAXN + 5];

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(v[i]);
    for (int i = 1; i <= min(n, m); ++i)//取的数不能超过 n 
        for (int j = 0; j <= i && i + j <= m; ++j) {
            //放的操作不能多于取的操作，且加起来不能超过 m 次操作 
            f[i][j] = -INF;
            if (j >= 1) f[i][j] = max(f[i][j], f[i - 1][j - 1]);//注意边界 
            if (j <= i - 1) f[i][j] = max(f[i][j], f[i - 1][j] + v[i]);
        }
    reverse(v + 1, v + n + 1);//翻转后做同样的 DP 
    for (int i = 1; i <= min(n, m); ++i)
        for (int j = 0; j <= i && i + j <= m; ++j) {
            g[i][j] = -INF;
            if (j >= 1) g[i][j] = max(g[i][j], g[i - 1][j - 1]);
            if (j <= i - 1) g[i][j] = max(g[i][j], g[i - 1][j] + v[i]);
        }
    for (int i = 0; i <= min(n, m); ++i)
        for (int j = 0; j <= i; ++j)
            for (int k = 0; k <= min(n, m); ++k)
                for (int l = 0; l <= k; ++l) {
                    if (i + j + k + l > m || i + k > n) break;
                    //加起来不能超过 m 次操作，
                    //且前面的数和后面的数不能重叠（加起来超过 n） 
                    ans = max(ans, f[i][j] + g[k][l]);//合并答案 
                }
    write(ans);
    putchar('\n');
    return 0;
}