BZOJ4300: 绝世好题

题目链接

走这里

题目分析

确实是绝世好题
喵？为什么大家都觉得是个裸DP……
_(:з」∠)_可能是我tcl，有了(O(n^2))的解之后一直没搞出优化到(log)级别的办法，最后还是看了博客

先说一下第一眼能得到的方程
(dp[i] = max(dp[j] + (a[i] & a[j] != 0) (1 <= j <= i))
但是发现这个玩意是(O(n^2))的，考虑如何优化
考虑什么时候两个数按位与的结果不是(0)，显然只要有一位上它们俩都是(1)就可以了，所以我们另外记录一个数组(mx[j])，表示处理到现在所有二进制下第(j)位是1的(a[k](1 <= k <= i))对应的(dp[i])的最大值
那么重新得到一个状态转移方程：
$dp[i] = max(mx[j]) + 1 (a[i]二进制表示下第j位是1) ( 因为)a_i <= 2 * 10 ^ 9(，所以我们的)j(只需要枚举到31即可 时间复杂度)O(nloga)$

代码

#include <bits/stdc++.h>
#define N (200000 + 10)
using namespace std;
inline int read() {
	int cnt = 0, f = 1; char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
	while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + c - '0'; c = getchar();}
	return cnt * f;
}
int n, a[N], dp[N], mx[100];
int ans = -1;
int main() {
	n = read();
	for (register int i = 1; i <= n; i++) a[i] = read();
	dp[1] = 1;
	for (register int i = 1; i <= n; i++){
		for (register int j = 0; j <= 31; j++) 
			if (a[i] & (1 << j)) dp[i] = max(dp[i], mx[j] + 1);
		for (register int j = 0; j <= 31; j++)
			if (a[i] & (1 << j)) mx[j] = max(dp[i], mx[j]);
		ans = max (ans, dp[i]);
	}
	printf("%d", ans);
	return 0;
}