摧毁时间线 题解

题目分析

我们有一个长度为 $n$ 的时间线，每个时刻 $i$ 有一个值 $a_i$。还有三组控制器的位置 $x_i, y_i, z_i$。

移除时刻 $i$ 的能量消耗为：

$$(a_{i-1}' - x_i)^2 + (a_i - y_{i+1})^2 + (a_{i+1}' - z_{i+2})^2 $$

其中 $a_{i-1}'$ 表示：如果 $i-1$ 这个时刻还没有被移除，则为 $a_{i-1}$，否则为 $0$。$a_{i+1}'$ 同理。

目标是找到一个移除顺序，使得总能量消耗最大。

关键洞察：如果我们考虑最后被移除的时刻，它会将时间线分成左右两个独立的子区间。这是典型的区间 DP 结构。

算法设计

状态定义

设 $dp[l][r][left][right]$ 表示将原始区间 $[l, r]$ 内的所有时刻移除所能获得的最大总能量，其中：

• $left = 1$ 表示 $a_{l-1}$ 可用（还没被移除），$0$ 表示不可用（已被移除或不存在）
• $right = 1$ 表示 $a_{r+1}$ 可用，$0$ 表示不可用

状态转移

枚举区间 $[l, r]$ 中最后一个被移除的时刻 $k$：

1. 移除 $k$ 时，$a_{k-1}'$ 可用的条件是：$k = l$ 且 $left = 1$
2. $a_{k+1}'$ 可用的条件是：$k = r$ 且 $right = 1$

移除 $k$ 的代价为：

$$cost = (A - x_k)^2 + (a_k - y_{k+1})^2 + (B - z_{k+2})^2 $$

其中：

• $A = a_{k-1}$ （如果 $a_{k-1}'$ 可用），否则 $A = 0$
• $B = a_{k+1}$ （如果 $a_{k+1}'$ 可用），否则 $B = 0$

总能量为：

$$dp[l][r][left][right] = \max_{k=l}^{r} \left[ dp[l][k-1][left][0] + dp[k+1][r][0][right] + cost \right] $$

边界条件

• 当 $l > r$ 时，返回 $0$
• 初始调用：$dp[1][n][1][1]$（整个区间的左右邻居都存在且值为 $0$）
• 需要处理好边界下标，设置 $a_0 = a_{n+1} = 0$，$y_{n+1} = z_{n+1} = z_{n+2} = 0$

复杂度分析

• 状态数：$O(n^2 \times 4)$
• 每个状态转移：$O(n)$
• 总时间复杂度：$O(n^3)$，在 $n \le 60$ 时完全可行
• 空间复杂度：$O(n^2)$

C++ 实现

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

typedef long long ll;
const ll INF = 1e18;
int n;
ll a[65], x[65], y[65], z[65];
ll dp[65][65][2][2];
bool vis[65][65][2][2];

ll dfs(int l, int r, int la, int ra) {
    if (l > r) return 0;
    if (vis[l][r][la][ra]) return dp[l][r][la][ra];
    
    ll &res = dp[l][r][la][ra];
    res = -INF;
    
    for (int k = l; k <= r; ++k) {
        // 计算移除 k 的代价
        ll A = 0, B = 0;
        if (k == l && la) A = a[l-1];       // a_{k-1} 可用
        if (k == r && ra) B = a[r+1];       // a_{k+1} 可用
        
        ll cost = (A - x[k]) * (A - x[k])
                + (a[k] - y[k+1]) * (a[k] - y[k+1])
                + (B - z[k+2]) * (B - z[k+2]);
        
        ll left_val = dfs(l, k-1, la, 0);   // 左边区间，右邻居不可用
        ll right_val = dfs(k+1, r, 0, ra);  // 右边区间，左邻居不可用
        res = max(res, left_val + right_val + cost);
    }
    
    vis[l][r][la][ra] = true;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> x[i];
    for (int i = 1; i <= n; ++i) cin >> y[i];
    for (int i = 1; i <= n; ++i) cin >> z[i];
    
    // 边界处理
    a[0] = a[n+1] = 0;
    y[n+1] = 0;
    z[n+1] = z[n+2] = 0;
    
    memset(vis, 0, sizeof(vis));
    
    // 初始状态：整个区间 [1, n]，左右邻居都存在（值为0）
    ll ans = dfs(1, n, 1, 1);
    
    cout << ans << endl;
    
    return 0;
}

算法标签

• 区间动态规划
• 记忆化搜索
• 最优化顺序问题
• 状态压缩