首页 > 代码库 > BZOJ 4300: 绝世好题

BZOJ 4300: 绝世好题

2024-09-01 00:18:08   218人阅读

Problem 4300. -- 绝世好题

4300: 绝世好题

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 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

Sample Output

2

HINT

 

n<=100000,ai<=2*10^9


 

 

Source

By Oxer

[Submit][Status][Discuss]

 

贪心，用$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: 绝世好题


联系
我们