J. Jewels Building 解题思路

核心问题分析

这是一道非常有趣的“炼金”游戏题。我们有一排初始能量的水晶数组 $A$ ，目标是把它融合成指定能量的数组 $B$ 。融合规则是：选定连续且能量相同的一段水晶，把它们融合成一颗能量为这段水晶长度的新水晶。值得注意的是，题目允许我们选择长度为 $1$ 的段（即 $l=r$ ），融合后它的能量就会变成 $1$ 。

初看这道题，水晶融合后能量变化极其不可控，感觉要搜的状态是一棵庞大无比的博弈树。但只要我们抓住了题目规则里的一个“漏洞”，这题就会瞬间变成一道优雅的 DP。

1. 拨开迷雾：万物皆可归“1”

规则里最反直觉的一点就是：单独一颗水晶，不论它原本能量是几，都可以自己跟自己融合，变成能量为 $1$ 的水晶。

这意味着什么？这意味着只要我们愿意，我们可以把初始数组 $A$ 里的所有水晶全部变成 $1$ ！一旦我们拥有了一排连续的 $1$ ，我们想要造出能量为 $x$ 的水晶简直易如反掌：只要把连续的 $x$ 个 $1$ 融合在一起，它们的长度是 $x$ ，自然就生成了一颗能量为 $x$ 的大水晶。

这引出了我们的第一个推论：任意一段长度为 $x$ 的水晶（无论初始值是多少），都可以被合成为一颗能量为 $x$ 的水晶。（消耗 $x$ 颗原始水晶）

那么问题来了，如果我想造一颗能量为 $x$ 的水晶，但我手头有连续的 $y$ 颗水晶（ $y > x$ ），我能把这 $y$ 颗全消耗掉，只产出一颗能量为 $x$ 的水晶吗？ 答案是可以的！ 我们可以用一种“反复横跳”的技巧来销毁多余的水晶：

先把这 $y$ 颗水晶全变成 $1$ 。
挑出相邻的 $2$ 颗 $1$ ，融合成一颗 $2$ 。
把这颗 $2$ 自己跟自己融合，又变回了 $1$ 。你看，经过这波操作，水晶总数巧妙地减少了 $1$ 颗！我们可以一直重复这个“销毁”过程，直到水晶数量正好剩下 $x$ 颗，然后再把它们一把融合成 $x$ 。

顿悟时刻： 只要我们在原数组 $A$ 中圈出任意一段长度 $L \ge x$ 的区间，我们绝对有办法把这段区间变成唯一的一颗能量为 $x$ 的水晶！

2. 动态规划的状态定义与两种选择

明确了上面的神仙性质后，我们发现要把 $A$ 变成 $B$ ，对于 $B$ 中的每一个目标水晶 $b_i$ ，我们要么：

白嫖（原石匹配）： 正好原数组当前的这颗水晶 $a_{k+1}$ 就等于 $b_i$ ，那我们什么都不用做，直接保留它。（消耗 $1$ 颗原始水晶）
硬造（熔炉重铸）： 利用上述的万能法则，划出一段长度 $L \ge b_i$ 的区间，强行把它捏成 $b_i$ 。（消耗 $L \ge b_i$ 颗原始水晶）

基于此，我们可以定义二维 DP： dp[i][j] 表示：能否成功构建出目标数组的前 $i$ 颗水晶 $b[1 \dots i]$ ，且恰好消耗了原数组的前 $j$ 颗水晶 $a[1 \dots j]$ 。

3. 贪心与转移优化

在写状态转移时，还有一个小贪心技巧。当我们在考虑第 $i$ 颗目标水晶时，如果是采取“白嫖”策略，我们只能严格基于上一层 dp[i-1][j] 为真的状态，看看 $a_{j+1}$ 等不等于 $b_i$ 。

但如果是采取“硬造”策略呢？硬造需要消耗 $\ge b_i$ 的长度。为了给后面的目标水晶留出尽可能多的原始水晶，我们显然希望前 $i-1$ 颗水晶消耗得越少越好！所以，我们只需要找到上一层能够成功的最小消耗 min_n。只要能满足最小消耗，那么接下来原数组从 min_n + b_i 一直到末尾 $n$ 的任何位置 $j$ ，都可以作为构建 $b_i$ 的合法结束点。

CPP 代码实现

cpp

// J. Jewels Building

#include <bits/stdc++.h>
#define lg(x) (63 - __builtin_clzll(x))
#define all(x) (x).begin(), (x).end()
#define low_bit(x) ((x) & (-x))
#define pb push_back
#define db long double
#define int long long
#define sz(x) (int)x.size()
#define endl "\n"

using namespace std;

const int INF = 2e18;

void solve() {

    int n, m;
    cin >> n >> m;
    vector<int> ns(n + 1), ms(m + 1);
    
    // dp[i][j] 代表完成目标数组前 i 个元素，消耗了原数组前 j 个元素
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    
    for (int i = 1; i <= n; i++) cin >> ns[i];
    for (int i = 1; i <= m; i++) cin >> ms[i];
    
    // 初始化边界：处理第 1 颗目标水晶
    // 策略 1：白嫖（如果第一颗恰好相等，消耗长度 1）
    if (ns[1] == ms[1]) {
        dp[1][1] = true;
    }
    // 策略 2：硬造（消耗任意 >= ms[1] 的长度，都可以捏出 ms[1]）
    for (int i = ms[1]; i <= n; i++) {
        dp[1][i] = true;
    }
    
    // 递推后续的目标水晶
    for (int i = 2; i <= m; i++) {
        int min_n = INF; // 记录完成前 i-1 个目标所消耗的最少原水晶数量
        
        for (int j = 1; j <= n; j++) {
            if (dp[i - 1][j]) {
                min_n = min(min_n, j); // 维护贪心最小值
                
                // 策略 1 转移：白嫖匹配
                if (j + 1 > n) continue;
                if (ns[j + 1] == ms[i]) {
                    dp[i][j + 1] = true;
                }
            }
        }
        
        // 策略 2 转移：硬造
        // 只要基于前置状态的最小消耗 min_n，再额外拨出 >= ms[i] 的长度即可
        for (int j = min_n + ms[i]; j <= n; j++) {
            dp[i][j] = true;
        }
    }
    
    // 只要存在一种方案，恰好把原数组 n 颗水晶全消耗完并造出 m 颗目标水晶，即为成功
    if (dp[m][n]) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    
}

signed main() {

    // 优化输入输出流
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t; 
    
    while (t--) {
        solve();
    }
    
}

J. Jewels Building 解题思路 ​

核心问题分析 ​

1. 拨开迷雾：万物皆可归“1” ​

2. 动态规划的状态定义与两种选择 ​

3. 贪心与转移优化 ​

CPP 代码实现 ​