为什么要写这道题呢?因为它是"绝世好题".
题意:给定n个数,在其中找出一段子序列b,使得b[i]&b[i-1]!=0,求出满足条件的最长子序列长度.
输入:第一行:一个整数n,表示数列的个数.
第二行:n个整数,表示数列a.
输出:一行,一个整数,表示最长的子序列长度.
解析:若b[i]&b[i-1]!=0,即b[i]与b[i-1]在二进制下有一位相同且都为1.那么设dp[i]表示前i个数所能达到的最长子序列长度,那么在转移时只需枚举是从二进制下的第几位转移过来的便好了.由于在转移时还要枚举是从哪个位置转移过来的,所以时间复杂度为o(n^2log(n)),但由于每次进行转移时是在前面的状态中找一个最大的,所以显然可以用堆进行优化,时间复杂度(o(nlog(n)^2)).(这题其实有o(nlog(n))的做法,而且大家好像都是这么写的,可我做的时候没想到(果然我还是菜!)).