题解：P10197 [USACO24FEB] Minimum Sum of Maximums P

· · 题解

将非固定位置按极长段考虑，可发现段内单调。

对于一个极长段 1<l<r<n，其贡献为：

\sum\limits_{i=l+1}^{r-1} a_i+\max(a_l,a_r)+\max(a_l,a_{l-1})+\max(a_r,a_{r+1})

注意到只需考虑两端的贡献，于是转而对值域区间考虑，求解的同时判定是否存在对应的填数方案。

注意到每段的值域区间不交或包含，考虑对区间树 DP，设 f_{S,l,r} 表示编号在 S 内的段值域全在 [l,r] 内的最小贡献，暴力转移复杂度 O(n^33^m)。

注意到一个子树内选的点一定可以调整为一段连续区间，于是可优化至 O(n^23^m)。

const int N = 305, M = 1 << 7, K = 7, inf = 1e9;
int n, m, U, a[N], s[M], a1[N], f[M][N][N];
bool tag[N];
struct seg {
    int l, r, k;
} b[K];
inline int F(int x, int u, int v) {
    return (b[x].l != inf) * max(b[x].l, u) + (b[x].r != inf) * max(b[x].r, v);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n1, m1;
    cin >> n1 >> m1;
    for (int i = 1; i <= n1; i++)
        cin >> a1[i];
    int x, lst = 0, bs = 0;
    while (m1--)
        cin >> x, tag[x] = 1;
    for (int i = 1, lst = 0; i <= n1; i++) {
        if (i < n1 && tag[i] && tag[i + 1])
            bs += max(a1[i], a1[i + 1]);
        if (tag[i]) {
            lst = i;
            continue;
        }
        bs += (a[++n] = a1[i]);
        if (i == n1 || tag[i + 1])
            b[m++] = {!lst ? inf : a1[lst], i == n1 ? inf : a1[i + 1], i - lst};
    }
    sort(a + 1, a + n + 1), U = 1 << m;
    for (int S = 1, T; S < U; S++)
        T = S & -S, s[S] = s[S ^ T] + b[__lg(T)].k;
    memset(f, 0x3f, sizeof f);
    memset(f[0], 0, sizeof f[0]);
    for (int S = 1; S < U; S++) {
        for (int l = n; l >= 1; l--) {
            for (int r = l; r <= n; r++) {
                if (r - l + 1 < s[S])
                    continue;
                auto u = a[l], v = a[r], &w = f[S][l][r] = min(f[S][l + 1][r], f[S][l][r - 1]);
                if (r - l + 1 == s[S])
                    for (int i = 0; i < m; i++)
                        if (S >> i & 1 && r - l + 1 - s[S ^ (1 << i)] >= b[i].k)
                            MIN(w, f[S ^ (1 << i)][l][r] - u - (l != r)*v + min(F(i, u, v), F(i, v, u)) + (l != r)*max(u, v));
                for (int T = S; T; T = T - 1 & S)
                    MIN(w, f[T][l][l + s[T] - 1] + f[S ^ T][l + s[T]][r]);
            }
        }
    }
    cout << f[U - 1][1][n] + bs << '\n';
    return 0;
}