首页 > 2017 四川省赛 E.Longest Increasing Subsequence【思维+贪心】

四川_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小时内删除。