当前位置: 首页 > news >正文

14 收心赛3 T1 最长不降子序列 题解

最长不降子序列

题面

小 W 有一个长度为 \(n\) 的序列 \(a_1, a_2 ...a_n\) ,且 \(a_i\) 的取值都为 1 或 2

现在,你可以任意选择该序列的一个区间进行翻转操作,但你只能翻转一次。

小 W 希望执行操作之后,整个序列的最长不下降子序列长度最大。请你求出这个最大值。

\(1 \le n \le 10^6\)

题解

这道题正解比较简单,考场上没有想到比较巧妙的思路,只能暴力dp,分数还好是拿到了,但是两个小时也过去了

暴力dp的思路就不说了,赛后看了看发现好像有点问题

假如我们不能翻转,那么最长不降子序列答案应该形如 \(111 ... 222 ...\)

如果能够翻转一次,那么答案应该形如 \(111 ... 222 ... 111 ... 222 ...\)

只要翻转中间的 $222 ... 111 ... $ 这一段即可转化为一个最长不降子序列

所以我们可以考虑每个点在哪一段,然后分别转移

\(f(i,1/2/3/4)\) 表示到第 \(i\) 个点,且第 \(i\) 个点在 \(1/2/3/4\) 段的最长不降子序列长度

转移

  • \(f(i,1) = f(i - 1, 1) + [a_i =1]\)
  • \(f(i,2) = max\{ f(i - 1, 2) ,f(i - 1, 1) \} + [a_i = 2]\)
  • \(f(i,3) = max\{f(i - 1, 3), f(i - 1, 2) \} + [a_i = 1]\)
  • \(f(i,4) = max \{f(i - 1, 4) , f(i - 1, 3)\} + [a_i = 2]\)

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;const int N = 1e6 + 10;int a[N], n;
int f[N][5];int main () {// freopen ("sequence.in", "r", stdin);// freopen ("sequence.out", "w", stdout);cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++) {for (int j = 1; j <= 4; j++) {f[i][j] = max (f[i - 1][j - 1], f[i - 1][j]) + ((a[i] & 1) == (j & 1));}}cout << max ({f[n][1], f[n][2], f[n][3], f[n][4]}) << endl;return 0;
}
http://www.hskmm.com/?act=detail&tid=25006

相关文章:

  • 16 LCA模拟赛1T1 密码 题解
  • 吴恩达深度学习课程一:神经网络和深度学习 第二周:神经网络基础(一)
  • 阿里开源规则引擎QLExpress
  • QOJ7411 Bitwise Xor
  • 完整教程:SOC-ESP32S3部分:25-HTTP请求
  • 为什么要采用“接口 - 抽象类 - 实现类”这种三层结构? - 浪矢
  • 对外提供 AI 服务的风险:合规视角与 AI 安全围栏落地指南
  • VScode C/C++ 汉化 竞赛版 只需下载扩展 (超简单)
  • 网络安全工具与社区讨论月报
  • 机器人运动未来与人机交互研究
  • 欧拉路径 欧拉图 小记
  • OI 笑传 #16
  • cf296b
  • 第一次使用Ttpora
  • Apache反向代理
  • 原版 Sunshine+虚拟显示器实现熄屏串流
  • 2025国庆Day4
  • gis坐标计算
  • day17 课程()
  • NKOJ全TJ计划——NP11744
  • ROIR 2025
  • trick 小记
  • python编写AI生常用匡架及使用指令集
  • 123123
  • 1005模拟赛总结
  • 2025.10.5 2024CCPC郑州
  • 20250531MATLAB三维绘图 - 教程
  • 概率期望dp 复习笔记
  • 2025.10
  • PCIe扫盲——物理层逻辑部分基础(一)