关于nlogn求LCS

P1439 【模板】最长公共子序列

水星湖 @ 2024-06-09 00:07:16

是否所有情况都适用?还是只有没有重复数字才适用


by Luka__Modric @ 2024-06-09 00:08:41

@水星湖 肯定所有情况都适用啊


by hdkk @ 2024-06-09 00:13:54

@Luka__Modric 呃呃,有重复数字还怎么转成LIS n log n求?


by hdkk @ 2024-06-09 00:17:32

@水星湖 感觉是只有 n^2 dp做法


by 水星湖 @ 2024-06-09 00:19:36

@hdkk 我想了一下,感觉有重复数字也可以吧


by 水星湖 @ 2024-06-09 00:20:37

@hdkk mp[i][j]表示i第j次出现对应的编号,然后很容易对另一个序列编号吧


by Luka__Modric @ 2024-06-09 00:21:40

@hdkk 是这样的,我糖了


by hdkk @ 2024-06-09 00:23:29

@水星湖 这么编号是错的


by hdkk @ 2024-06-09 00:24:35

@水星湖 hack:

1 2 1

2 1 3


by 水星湖 @ 2024-06-09 00:28:39

@hdkk


by hdkk @ 2024-06-09 00:29:51

@水星湖 你怎么把 3 编号成 3


| 下一页