四川_E4L,2017 四川省赛 E.Longest Increasing Subsequence【思维+贪心】
互联网
2021-01-19 04:06:19
题面下载：https://icpc-camp-cdn.b0.upaiyun.com/permanent/problems/sichuan-2017.pdf
题目大意：
给你N个数组成的序列，现在规定F【i】表示的是以a【i】结尾的最长上升子序列长度。
LIS（1）表示的是删除第一个数之后，F【i】的亦或和。
现在然你求LIS（1~N）；
思路：
删除第i个数，对他前边的数的F【j】没有影响，他后边的数的F【j】，要么还是F【j】，亦或者是F【j】-1；
那么我们首先nlogn去预处理出F【i】。
然后分两种情况考虑：
①当F【j】依旧为F【j】的时候，那么说明位子j前边存在某些位子使得F【x】=F【j】-1&&a【x】
免责声明：非本网注明原创的信息，皆为程序自动获取自互联网，目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责；如此页面有侵犯到您的权益，请给站长发送邮件，并提供相关证明(版权证明、身份证正反面、侵权链接)，站长将在收到邮件24小时内删除。