【洛谷】4310: 绝世好题【二进制DP】

时间:2022-04-23 16:18:54

P4310 绝世好题

题目描述

给定一个长度为n的数列ai,求ai的子序列bi的最长长度,满足bi&bi-1!=0(2<=i<=len)。

输入输出格式

输入格式:

输入文件共2行。 第一行包括一个整数n。 第二行包括n个整数,第i个整数表示ai。

输出格式:

输出文件共一行。 包括一个整数,表示子序列bi的最长长度。

输入输出样例

输入样例#1: 复制
3
1 2 3
输出样例#1: 复制
2

说明

对于100%的数据,1<=n<=100000,ai<=10^9。


Solution

相邻与不为0,意思就是当前选择的和上一次选择的二进制拆位后至少有一位都是1

定义$dp[i]$表示序列最后一个数第$i$位为1的最优长度。

那么每枚举一个数,以它结尾能得到的最大值就是$max(dp[i]+1),(1<<i)&a == 1$转移过来,然后这个最大值可以反过去更新这些$dp[i]$

非常巧妙的二进制DP!学习一波!

Code

#include<bits/stdc++.h>
using namespace std; int a, n, dp[]; int main() {
scanf("%d", &n);
int ans = ;
for(int i = ; i <= n; i ++) {
scanf("%d", &a);
int k = ;
for(int c = ; c <= ; c ++)
if(( << c) & a) k = max(dp[c] + , k);
for(int c = ; c <= ; c ++)
if(( << c) & a) dp[c] = max(dp[c], k);
ans = max(ans, k);
}
printf("%d", ans);
return ;
}