P4310 绝世好题
题目描述
给定一个长度为n的数列ai，求ai的子序列bi的最长长度，满足bi&bi-1!=0(2<=i<=len)。
输入输出格式
输入格式：
输入文件共2行。 第一行包括一个整数n。 第二行包括n个整数，第i个整数表示ai。
输出格式：
输出文件共一行。 包括一个整数，表示子序列bi的最长长度。
输入输出样例
说明
对于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 ;
}