[USACO16OPEN] 248 G

题意

给出一个正整数序列。每次可以把一对相邻且相等的数字 x, x 合并成一个 x+1。

要求通过若干次操作，使整个过程中能出现的最大数字尽量大。

思路

最直接的办法是暴力枚举每一步合并哪一对相邻且相等的数字。

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37#include <bits/stdc++.h>
using namespace std;

int dfs(vector<int> v) {
    int best = 0;
    for (int x : v) {
        best = max(best, x);
    }

    for (int i = 0; i + 1 < (int)v.size(); ++i) {
        if (v[i] != v[i + 1]) {
            continue;
        }
        vector<int> next = v;
        next[i] = next[i] + 1;
        next.erase(next.begin() + i + 1);
        // 暴力枚举这一步合并哪一对相邻且相等的数字。
        best = max(best, dfs(next));
    }

    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    cout << dfs(v) << '\n';
    return 0;
}

brute.cpp 完整搜索所有合并顺序，适合小数据对拍，但正式数据下复杂度太高。

关键观察是：如果一个区间 [l, r] 最终能整体合成成某个值 v，那么最后一步一定是把它拆成两段：

[l, k] 先整体合成 v-1
[k+1, r] 也整体合成 v-1

然后这两个相邻且相等的值再合并成 v。

所以定义 dp[l][r] 表示区间 [l, r] 整体能合成出的最大值；如果不能整体合成，就记为 0。

这张表说明几个典型状态的含义：

状态	表示什么
`dp[3][3] = a[3]`	单个数字本身就是可合成结果
`dp[2][4] = 0`	区间 `[2, 4]` 不能整体压成一个数
`dp[2][4] = 3`	区间 `[2, 4]` 可以整体合成成一个 `3`

读这张表时，重点是理解 dp[l][r] 代表“整个区间最后只剩一个数”的结果，而不是“区间里能出现的最大数”。只有这个定义成立，断点转移才是正确的。

转移时枚举最后一次合并的断点 k。如果：

dp[l][k] == dp[k+1][r] != 0

那么：

dp[l][r] = max(dp[l][r], dp[l][k] + 1)

所有区间里出现过的最大值就是答案。

DP 公式

设 $dp_{l,r}$ 表示区间 $[l,r]$ 整体能合成出的最大值；若不能整体合成，则为 $0$ 。边界为：

dp_{i,i}=a_i

枚举最后一次合并的断点 $k$ 。当左右两段能合成相同值时：

\text{if }dp_{l,k}=dp_{k+1,r}\ne 0,\quad dp_{l,r}=\max(dp_{l,r},\ dp_{l,k}+1)

最终答案为所有区间状态中的最大值：

\max_{l\leqslant r} dp_{l,r}

公式解释：只有左右两段都能整体合成同一个值时，最后一步才能把它们合成更大的值。dp_{l,r}=0 表示这个区间不能整体压成一个数，因此不能作为有效前驱。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39#include <bits/stdc++.h>
using namespace std;

static int a[255];
static int dp[255][255];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        dp[i][i] = a[i];
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, a[i]);
    }

    // dp[l][r] 表示区间 [l, r] 能整体合成的最大值，0 表示不能整体合成。
    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            for (int k = l; k < r; ++k) {
                if (dp[l][k] == 0 || dp[l][k] != dp[k + 1][r]) {
                    continue;
                }
                dp[l][r] = max(dp[l][r], dp[l][k] + 1);
            }
            ans = max(ans, dp[l][r]);
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

区间 DP 需要枚举区间长度、左端点和断点，所以时间复杂度是 $O(N^3)$ ，空间复杂度是 $O(N^2)$ 。

总结

这题的关键不在于模拟合并顺序，而在于识别出“整体合成”的区间结构。只要抓住最后一步一定是两个相等子区间的合并，区间 DP 就很自然了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析