首页 > 代码库 > BZOJ 4300: 绝世好题
BZOJ 4300: 绝世好题
Problem 4300. -- 绝世好题
4300: 绝世好题
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 1597 Solved: 814
[Submit][Status][Discuss]
Description
给定一个长度为n的数列ai,求ai的子序列bi的最长长度,满足bi&bi-1!=0(2<=i<=len)。
Input
输入文件共2行。
第一行包括一个整数n。
第二行包括n个整数,第i个整数表示ai。
Output
输出文件共一行。
包括一个整数,表示子序列bi的最长长度。
Sample Input
3
1 2 3
1 2 3
Sample Output
2
HINT
n<=100000,ai<=2*10^9
Source
By Oxer
贪心,用$f[i]$表示结尾数字第i位上为1的最长子序列长度。
1 import java.util.Arrays; 2 import java.util.Scanner; 3 4 public class Main { 5 6 public static void main(String args[]) { 7 8 Scanner in = new Scanner(System.in); 9 10 int n = in.nextInt();11 int f[] = new int[35];12 13 Arrays.fill(f, 0);14 15 for (int i = 1; i <= n; ++i) {16 17 int num = in.nextInt(), tmp = 0;18 19 for (int j = 0; j <= 30; ++j)20 if (((num >> j) & 1) == 1)21 tmp = Math.max(tmp, f[j]);22 23 for (int j = 0; j <= 30; ++j)24 if (((num >> j) & 1) == 1)25 f[j] = Math.max(f[j], tmp + 1);26 27 }28 29 int ans = 0;30 31 for (int i = 0; i <= 30; ++i)32 ans = Math.max(ans, f[i]);33 34 System.out.println(ans);35 36 in.close();37 38 }39 40 }
@Author: YouSiki
BZOJ 4300: 绝世好题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。