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

A Twisty Movement

CF933A A Twisty Movement

简化题目

给定一个有 \(1\)\(2\) 两个数字组成的数组中,选择一个子串,将 \(1\) 变成 \(2\),将 \(2\) 变成 \(1\),求出变化后的序列的最长上升子序列。

思路

简单的情况

如果没有变换操作,题目就变成了一个简单的最长上升子序列问题,答案一定为

\[[1...1][2...2] \]

这种形式,设 \(f[i][1/2]\) 表示前 \(i\) 个数中,以 \(1\)\(2\) 这两个数字结尾的最长上升子序列。

转移为

\[f[i][1] = f[i-1][1] + (a[i] == 1) \]

\[f[i][2] = \max(f[i][1], f[i-1][2] + (a[i] == 2)) \]

题目转换

再考虑题目中的变换操作,可以知道这次的操作一定会对答案造成一定的变化,要不然这次的转换一定是无用的,不优的,考虑怎么翻转至 \([1...1][2...2]\) 这种状态。

  1. \([1...1]\) 这个区间内翻转,有 \([2...2][1...1][2...2]\) 这种情况,\([1...1]\) 长度可能为零
  2. \([2...2]\) 这个区间内翻转,有 \([1...1][2...2][1...1]\) 这种情况,\([2...2]\) 长度可能为零
  3. \([1...1][2...2]\) 中间翻转,先将 \([1...1][2...2]\) 划分成 \([1...1][1...1][2...2][2...2]\),再将中间的 \([1...1][2...2]\) 翻转成 \([2...2][1...1]\),变成了 \([1...1][2...2][1...1][2...2]\) 这种情况,其中中间的 \([2...2][1...1]\) 长度可能为零

由于长度都有可能为零,将这三种情况合并成一种,用 $$[1...1][2...2][1...1][2...2]$$ 表示,其中每一段都可以为空。

现在就可以 dp 了。

  • 状态:
    \(f[i][j]\) 表示以i为结尾的前 \(j + 1\) 段的最长满足条件的序列长度。

  • 转移:

  1. \(f[i][0] += (a[i] == 1)\)
  2. \(f[i][1] = max(f[i][0], f[i-1][1] + (a[i] == 2))\)
  3. \(f[i][1] = max(f[i][1], f[i-1][2] + (a[i] == 1))\)
  4. \(f[i][1] = max(f[i][2], f[i-1][3] + (a[i] == 2))\)
  • 答案:
    输出 \(f[n][4]\) 即可。

代码

int main() {for (int i = 1; i <= n; i++) cin >> a[i];scanf("%d", &n);for (int i = 1; i <= n; i++) {int a; scanf("%d", &a);f[i][0] = f[i - 1][0] + (a == 1);f[i][1] = max(f[i][0], f[i-1][1] + (a == 2));f[i][2] = max(f[i][1], f[i-1][2] + (a == 1));f[i][3] = max(f[i][2], f[i-1][3] + (a == 2));}int ans = 0;for (int i = 1; i <= n; i++)ans = max(ans, f[i][3]);printf("%d\n", ans);return 0;
}

个人反思

考试的思路

这道题在考试过程中,没有反应出最长上升子序列的模型,没有想到可以用动态规划的方式来解决,重点放在了区间的转换上和贪心,导致没能想出这道题目正确的解法。

怎么改正

  1. 问题转化:以后再看到 最长上升子序列 最长不下降子序列时等经典dp模型时要快速的明确这题的主体算法是动态规划,并将其转换为动规模型,其他算法也是如此。
  2. 算法思考:一定不要用同一个算法想太久,如果行不通要换一种算法在想想。
http://www.hskmm.com/?act=detail&tid=19130

相关文章:

  • 完整教程:iOS 混淆与反调试反 Hook 实战,运行时防护、注入检测与安全加固流程
  • Attention进阶史(MHA, MQA, GQA, MLA)
  • 2025北京个性旅行自由行口碑推荐北京汇通清源国际旅游公司,满足独特需求,自由随心
  • 2025推拉门品牌推荐榜:聚焦玻璃推拉门,钛镁合金推拉门选择指南
  • 9-27
  • 图解KV Cache
  • [K230学习笔记 00] 前言
  • 博弈论
  • [CEOI 2025] theseus 做题记录
  • 2025 年钣金加工厂家最新推荐排行榜发布:江门,珠三角钣金加工厂选择指南
  • 全文 -- Vortex: Extending the RISC-V ISA for GPGPU and 3D-Graphics Research - 指南
  • 2025.9.26 - 9.30
  • Codeforces Round 1053 (Div. 1) D. Attraction Theory
  • 通过AWS SSO设备代码认证进行AWS凭证钓鱼攻击(2024年更新)
  • 解码数据结构栈
  • 第七章 手写数字识别V4
  • 什么?你的蓝牙用不了了?
  • 模板库
  • 30.Linux DHCP 服务器 - 详解
  • [K230学习笔记] 前言
  • 集训队作业3——qoj#11723
  • 2025 年推拉门品牌推荐排行榜发布:聚焦玻璃推拉门,钛镁合金推拉门,厨房推拉门,阳台推拉门,淋浴隔断推拉门选择指南!
  • 2025.9.27比赛总结
  • [K230学习笔记] 目录
  • 116.飞行员兄弟
  • 2025系统门窗品牌推荐榜单发布,吉缘等一线品质品牌隔音节能实力解析
  • 课程总结(作业2)
  • 旅游管理虚拟仿真实训室:打通理论与实践壁垒 - 详解
  • 【光照】[PBR][漫反射]实现方法对比
  • Xpath 提取数据