Slastičarnica 题解

题目分析

我们有一个长度为 $n$ 的序列 $a_1, \ldots, a_n$，需要进行 $q$ 次操作。每次操作要求删除一个长度为 $d_i$ 的前缀或后缀，且该前缀/后缀中的所有元素都必须 $\geq s_i$。

在每次操作前，我们可以任意删除一个前缀或后缀（可以为空），这给了我们调整序列的灵活性。

目标是最大化能成功执行的操作次数。

关键观察

1. 操作的本质：每次操作实际上是要求序列的某个端部存在一个长度为 $d_i$ 的连续子数组，其中所有元素 $\geq s_i$。

2. 预处理的重要性：由于 $n \leq 5000$ 但 $q \leq 2 \times 10^5$，我们需要预处理信息来快速回答查询。

3. 动态规划思路：我们可以预处理对于每个可能的子数组，从该子数组开始最多能完成多少次操作。

算法思路

1. 预处理

对于每个子数组 $[l, r]$，我们预处理：

• 前缀最小值：快速判断前缀是否满足条件
• 后缀最小值：快速判断后缀是否满足条件
• 从该子数组开始能完成的最大操作数

2. 状态定义

设 $dp[l][r]$ 表示当前剩余子数组为 $[l, r]$ 时，从该状态开始最多能完成的操作次数。

3. 状态转移

对于每个状态 $[l, r]$，考虑所有可能的操作：

• 如果可以通过删除一些前缀/后缀使得操作 $i$ 可行，则转移到新的状态
• 取所有可能转移中的最大值

4. 优化

由于 $n \leq 5000$，$O(n^2)$ 的 DP 是可行的，但需要优化转移过程。

C++ 实现

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

const int MAXN = 5005;
const int MAXQ = 200005;

int n, q;
int a[MAXN];
int pre_min[MAXN][MAXN];  // pre_min[i][j]: 子数组[i,j]的前缀最小值
int suf_min[MAXN][MAXN];  // suf_min[i][j]: 子数组[i,j]的后缀最小值
int dp[MAXN][MAXN];       // dp[l][r]: 从子数组[l,r]开始的最大操作数
vector<pair<int, int>> operations;  // 存储所有操作 (d_i, s_i)

// 预处理前缀最小值和后缀最小值
void precompute_min() {
    for (int i = 1; i <= n; i++) {
        pre_min[i][i] = a[i];
        for (int j = i + 1; j <= n; j++) {
            pre_min[i][j] = min(pre_min[i][j-1], a[j]);
        }
    }
    
    for (int i = 1; i <= n; i++) {
        suf_min[i][i] = a[i];
        for (int j = i - 1; j >= 1; j--) {
            suf_min[j][i] = min(suf_min[j+1][i], a[j]);
        }
    }
}

// 检查操作是否可行
bool can_remove_prefix(int l, int r, int d, int s) {
    if (r - l + 1 < d) return false;
    return pre_min[l][l + d - 1] >= s;
}

bool can_remove_suffix(int l, int r, int d, int s) {
    if (r - l + 1 < d) return false;
    return suf_min[r - d + 1][r] >= s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    operations.resize(q);
    for (int i = 0; i < q; i++) {
        cin >> operations[i].first >> operations[i].second;
    }
    
    precompute_min();
    
    // 初始化DP
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            dp[i][j] = 0;
        }
    }
    
    // 按子数组长度从小到大计算DP
    for (int len = 1; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            
            // 尝试每个操作
            for (int op_idx = 0; op_idx < q; op_idx++) {
                int d = operations[op_idx].first;
                int s = operations[op_idx].second;
                
                // 尝试删除前缀
                if (can_remove_prefix(l, r, d, s)) {
                    int new_l = l + d;
                    if (new_l <= r) {
                        dp[l][r] = max(dp[l][r], 1 + dp[new_l][r]);
                    } else {
                        dp[l][r] = max(dp[l][r], 1);
                    }
                }
                
                // 尝试删除后缀
                if (can_remove_suffix(l, r, d, s)) {
                    int new_r = r - d;
                    if (l <= new_r) {
                        dp[l][r] = max(dp[l][r], 1 + dp[l][new_r]);
                    } else {
                        dp[l][r] = max(dp[l][r], 1);
                    }
                }
            }
            
            // 尝试先删除一些前缀/后缀再执行操作
            for (int cut = 0; cut <= len; cut++) {
                // 删除前缀
                if (cut > 0) {
                    dp[l][r] = max(dp[l][r], dp[l + cut][r]);
                }
                // 删除后缀
                if (cut < len) {
                    dp[l][r] = max(dp[l][r], dp[l][r - cut]);
                }
            }
        }
    }
    
    cout << dp[1][n] << endl;
    
    return 0;
}

算法优化

上面的基础实现可能对于最大数据范围仍然较慢。我们可以进一步优化：

1. 操作预处理

预处理每个操作对于每个可能子数组的可行性。

2. 状态压缩

注意到我们只关心从整个序列开始能完成的操作数，可以优化状态表示。

3. 贪心策略

对于某些特殊情况（如子任务2），可以使用更简单的贪心策略。

复杂度分析

• 预处理：$O(n^2)$
• DP计算：$O(n^2 \cdot q)$（基础版本）
• 优化后：$O(n^2 + n \cdot q)$

关键技巧

1. 预处理最小值：快速判断前缀/后缀是否满足条件
2. 动态规划状态设计：以子数组为状态，避免重复计算
3. 操作顺序处理：考虑所有可能的操作顺序

样例验证

样例1

输入：
5 6
1 2 3 4 5
1 1
1 2
1 3
1 4
1 6
1 5
输出：4

样例2

输入：
5 3
1 3 2 2 1
3 1
1 3
2 2
输出：2

样例3

输入：
9 5
1 3 2 5 1 4 6 2 1
3 2
2 3
1 1
1 2
1 1
输出：4

这个解法利用了动态规划和预处理技术，能够在合理时间内解决中等规模的问题。对于更大的数据范围，可能需要进一步的优化。