题解：Minimum Sum of Maximum Maximums

核心思路解析

本题的关键在于通过动态规划（DP）处理可交换瓷砖的最优排列，同时利用固定瓷砖的位置约束，最小化相邻瓷砖最大最大丑陋度之和。

核心公式转化：

• 原目标是最小化 $\sum \max(a_i, a_{i+1})$
• 通过数学变换可转化为 $\frac{1}{2} \left( \sum (a_i + a_{i+1}) + \sum |a_i - a_{i+1}| \right)$
• 前半部分 $\sum (a_i + a_{i+1})$ 是固定值（与排列无关），因此只需最小化 $\sum |a_i - a_{i+1}|$

算法步骤

1. 划分固定与可变瓷砖：

   • 固定瓷砖位置：$X[1..m]$（加上边界 $X[0]=0$ 和 $X[m+1]=n+1$）
   • 可变瓷砖：收集所有未固定的瓷砖值，排序后存入 $V$

2. 状态定义：

   • $f[s][i]$：用状态 $s$ 表示已处理的固定瓷砖间隔，且从 $V[i]$ 开始放置瓷砖的最小代价
   • $s$ 是二进制掩码，第 $j$ 位为 1 表示处理了 $X[j]$ 与 $X[j+1]$ 之间的间隔

3. 状态转移：

   • 对于每个状态 $s$，枚举其子集 $s2$ 进行分割转移
   • 对每个间隔 $j$，计算放置瓷砖的代价 $val(j, A, B)$（$A,B$ 为间隔两端的瓷砖值）

4. 最终计算：

   • 结合固定间隔的基础代价和 DP 结果，按转化公式计算最小总丑陋度

代码解析

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, m, X[8];  // X存储固定瓷砖位置（含边界）
const ll I = 1e13;  // 边界虚拟值
ll a[310];  // 原始丑陋度数组
vector<ll>V;  // 存储可交换瓷砖的值（排序后）
bool vp[310];  // 标记是否为固定瓷砖
ll f[1 << 8][310];  // DP状态：f[状态][起始位置] = 最小代价
const ll II = 1e18;  // 无穷大
int sz[1 << 8];  // 存储每个状态需要的瓷砖数量

// 更新最小值
void ad(ll &x, ll y) {
    if (x > y) x = y;
}

// 计算间隔j的代价：A和B分别为间隔内瓷砖的最小值和最大值
ll val(int e, ll A, ll B) {
    ll x = a[X[e]], y = a[X[e + 1]];
    if (x > y) swap(x, y);  // 确保x <= y
    if (A > B) swap(A, B);  // 确保A <= B
    return abs(x - A) + abs(y - B) + B - A;
}

int main() {
    scanf("%d%d", &n, &m);
    ll zt = 0;  // 计算固定部分总和：sum(a_i + a_{i+1})

    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        zt += a[i] * 2;  // 每个a_i在sum中出现两次（除首尾）
    }

    // 处理边界虚拟值
    a[0] = a[n + 1] = I;
    zt += I * 2;

    // 读取固定瓷砖位置
    for (int i = 1; i <= m; i++) {
        scanf("%d", &X[i]);
        vp[X[i]] = 1;  // 标记为固定
    }
    X[0] = 0;  // 左边界
    X[m + 1] = n + 1;  // 右边界

    // 收集可交换瓷砖的值并排序
    for (int i = 1; i <= n; i++) {
        if (!vp[i]) V.push_back(a[i]);
    }
    sort(V.begin(), V.end());
    n = V.size();  // 更新n为可交换瓷砖数量

    // 处理相邻固定瓷砖的间隔（无需放置瓷砖）
    int cs = 0;  // 标记相邻固定瓷砖的状态
    ll eg = 0;   // 相邻固定瓷砖的代价
    for (int i = 0; i <= m; i++) {
        if (X[i] + 1 == X[i + 1]) {
            cs |= (1 << i);  // 标记该间隔无需放置瓷砖
            eg += abs(a[X[i]] - a[X[i + 1]]);  // 直接计算代价
        }
    }

    // 初始化DP
    for (int s = 0; s < (1 << (m + 1)); s++) {
        if (s & cs) continue;  // 跳过包含相邻固定瓷砖的状态

        // 计算状态s需要的瓷砖数量
        sz[s] = 0;
        for (int i = 0; i <= m; i++) {
            if ((s >> i) & 1) {
                sz[s] += X[i + 1] - X[i] - 1;  // 间隔内的瓷砖数
            }
        }

        // 初始化DP值为无穷大
        for (int i = 0; i <= n; i++) {
            f[s][i] = II;
        }

        // 处理当前状态
        for (int i = 0; i + sz[s] <= n; i++) {
            if (sz[s] == 0) {
                f[s][i] = 0;  // 无需放置瓷砖，代价为0
                continue;
            }

            // 分割状态s为s2和s^s2，合并结果
            for (int s2 = (s - 1) & s; s2; s2 = (s2 - 1) & s) {
                ad(f[s][i], f[s2][i] + f[s ^ s2][i + sz[s2]]);
            }

            // 直接处理单个间隔j
            for (int j = 0; j <= m; j++) {
                if ((s >> j) & 1) {  // 状态s包含间隔j
                    ll va = val(j, V[i], V[i + sz[s] - 1]);  // 计算间隔j的代价
                    // 枚举间隔内的瓷砖分配
                    for (int k = 0; k < X[j + 1] - X[j]; k++) {
                        ad(f[s][i], f[s ^ (1 << j)][i + k] + va);
                    }
                }
            }
        }
    }

    // 计算最终结果：按转化公式计算
    printf("%lld", (zt + f[cs ^ ((1 << (m + 1)) - 1)][0] + eg) / 2 - I * 2);
    return 0;
}

复杂度分析

• 状态数：$O(2^{m+1} \cdot N)$，其中 $m \leq 6$，故 $2^7 = 128$ 种状态
• 转移复杂度：每个状态枚举子集和间隔，总复杂度约 $O(2^m \cdot N \cdot m)$
• 整体复杂度：$O(N \cdot m \cdot 2^m)$，对于 $N=300$ 和 $m=6$ 可高效运行

该算法通过状态压缩DP处理固定间隔约束，结合数学转化简化问题，最终高效求解最小总丑陋度。