题解 CF1062A 【A Prank】
本题解与其他题解思路不同 ## Explanation 对于某个序列，找出一个最大的子序列，保证该子序列位置不存在其他可能序列。 坑点来了: > 序列需要满足如下要求： > - 序列必须是**连续**的**一个**子序列 > - 序列中的元素 $x$ 满足 **$x \in [1,10 ^ 3]$** ~~这个题意搞了半天没读懂什么意思..去了趟厕所回来才醒悟~~  血泪史 (大哭) ## Solution 实际上我们不难发现，如果一段序列 $a_l \sim a_r$ 是可以删除的话，那么我们只要保证 $a_{l - 1}$ 和 $a_{r + 1}$ 的差值为 $(r + 1) - (l - 1) + 1$ 即可 所以不难找出方法： **对于 $i \in [1 , n]$，找出每个 $a_i$ 所能删除的最大子区间** 所以我们只要对每个 $a_r, r \in [1 , n]$ 枚举左端点就可以了 对于可行的左端点 $a_l$ 满足区间长度为 $r - l - 1$ 注意特判两个边界 $1$ 和 $1000$ > 序列中的元素 $x$ 满足 **$x \in [1,10 ^ 3]$** 用 $f_i$ 记录 $a_i$ 的区间长度，最后取最大值就可以了 ## AC Code _(C language)_ ```cpp #include <stdio.h> int a[105], ans, n, f[105]; inline void solve() { a[n + 1] = 1001; for(int i = 1; i <= n + 1; ++i) { for(int j = 0; j < i; ++j) if(a[i] - a[j] == i - j) f[i] = i - j - 1 > f[i] ? i - j - 1 : f[i]; } for(int i = 1;i <= n + 1; ++i) ans = f[i] > ans ? f[i] : ans; } int main() { scanf("%d", &n); for(int i = 1;i <= n;++i) scanf("%d", &a[i]); solve(); printf("%d\n", ans); return 0; } ```
<<< Return to archive list