专栏首页数据结构与算法BZOJ4300: 绝世好题(dp)

BZOJ4300: 绝世好题(dp)

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 2751  Solved: 1493

[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

题目简洁好评

$n^2$的dp比较无脑,但是肯定过不了

刚开始我以为这玩意儿有决策单调性,但是很显然是错的。。

正解充分利用了$&$的性质,我们直接用$f[i]$表示第$i$位不为$0$时的最大值

转移的时候枚举这一位是不是$0$就可以了

#include<cstdio>
#include<algorithm>
#define int long long 
using namespace std;
const int MAXN = 1e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int a[MAXN], f[33], B = 32;
main() {
    int N = read(), out = 0;
    for(int i = 1; i <= N; i++) a[i] = read();
    for(int i = 1; i <= N; i++) {
        int ans = 0;
        for(int j = B; j >= 0; j--) 
            if(a[i] & (1 << j))
                ans = max(ans, f[j] + 1);
        for(int j = B; j >= 0; j--)
            if(a[i] & (1 << j))
                f[j] = ans;
    }
    for(int i = 0; i <= B; i++) 
        out = max(out, f[i]);
    printf("%d", out);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P1903 【模板】分块/带修改莫队(数颜色)

    题目描述 墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到...

    attack
  • 2017.10.27涩会题大乱斗部分题解

    A  P3741 honoka的键盘 和昨天的T1一样, 枚举改哪一个 1 #include<cstdio> 2 #include<cstring> 3 ...

    attack
  • 洛谷P5245 【模板】多项式快速幂(多项式ln 多项式exp)

    attack
  • 【C语言笔记】函数参数压栈的顺序?

    按照日常习惯来看,C语言的函数参数压栈顺序是从左到右吧?但是事实却是相反的,C语言函数参数压栈顺序是从右到左的。下面看一个程序:

    正念君
  • 【USACO 1.2】Palindromic Squares

    饶文津
  • P1903 【模板】分块/带修改莫队(数颜色)

    题目描述 墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到...

    attack
  • HDU 3488 Tour(拆点+二分图最大权匹配--KM)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3488

    Ch_Zaqdt
  • CSU 1326: The contest(分组背包)

    http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1326 题意:       n个题目,每个题目都有一个价值P...

    用户1624346
  • 2017年中国大学生程序设计竞赛-中南地区赛暨第八届湘潭市大学生计算机程序设计大赛题解&源码(A.高斯消元,D,模拟,E,前缀和,F,LCS,H,Prim算法,I,胡搞,J,树状数组)

    A-------------------------------------------------------------------------------...

    Angel_Kitty
  • 「2017 Multi-University Training Contest 2」2017多校训练2

    给定数组a[1..n]和b[1..n],b[i]在[1~n]内。要得到a[n+1..2n],每次选b数组的一个,令a[i]为j=b[k]到i-1位置中最大的a[...

    饶文津

扫码关注云+社区

领取腾讯云代金券