noip t3 特殊性质贪心求证伪
  • 板块学术版
  • 楼主lanretE
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/19 09:27
  • 上次更新2023/11/19 11:46:58
查看原帖
noip t3 特殊性质贪心求证伪
398190
lanretE楼主2023/11/19 09:27

首先因为 x1<y1,从 x1 开始找最长不上升子串,设最后可以到 xk,那么这个子串里面的 x 都小于 y1,用 y1 匹配,然后用 xk 匹配 y2~ym-1,剩下的 xk+1~xn 用最大的 ym 匹配

同样的,由于 xn 是最小值,从 y1 开始找 LIS,最后到 yk,x1 小于 LDS 里面所有 y,然后用 yk 匹配 x2~xn-1,最后用 xn 匹配 yk+1~ym

这玩意考场上瞎想的,能不能给个反例

2023/11/19 09:27
加载中...