acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • T2-2 信号的最佳共鸣

    核心思想 这是一道最长公共子序列(LCS)的变形题,不是求长度,而是求对应位置乘积和的最大值。 状态定义 * i 遍历序列A(0到N) * j 遍历序列B(0到M) * 初始值:全部设为 -INF(表示还没有合法方案) 状态转移(核心) 对于每个位置 (i, j),有三种决策: 1️⃣ 不选A[I](跳过A的当前数) 从 (i-1, j) 转移过来,相当于A往前退一步 2️⃣ 不选B[J](跳过B的当前数) 从 (i, j-1) 转移过来,相当于B往前退一步 3️⃣ 选择A[I]和B[J]配对(关键) 这一步有两种可能: a) 这是第一对数 直接用这一对的乘积作为结果(满足"至少选1对") b) 累加到之前的结果 如果 (i-1, j-1) 已经有合法方案,就累加当前这对的乘积 为什么这样写? 关键点1:自动处理"至少1对" * 不用单独记录选了几对(省去第三维) * 初始化为 -INF,只有真正配对后才有有效值 * 每次配对都考虑"作为第一对"或"累加到已有结果" 关键点2:保持子序列顺序 * dp[i-1][j-1] 确保了配对的两个数都是按原序列顺序选的 * 类似LCS,对角线转移保证顺序性 图解样例1 DP表推导(部分关键值): 代码

    userId_undefined
    知予
    倔强青铜
    4阅读
    0回复
    0点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页